目录
-
1. poj 2236 Wireless Network
-
2. poj 1611 The Suspects
-
3. hdu 1213 How Many Tables
-
4. hdu 3038 How Many Answers Are Wrong
-
5. poj 1182 食物链
-
6. poj 1417 True Liars
-
7. poj 1456 Supermarket
-
8. poj 1733 Parity game
-
9. poj1984 Navigation Nightmare
-
10. poj 2912 A Bug’s Life
-
11. poj 2912 Rochambeau
-
12. ZOJ-3261 Connections in Galaxy War
-
13. hdu 1272 小希的迷宫
-
14. poj 1308 Is It A Tree?
1. poj 2236 Wireless Network
- 水题
#include <iostream>
using namespace std;
const int MAXN = 2e5+100;
int set[MAXN];
int rank[MAXN];
struct NODE{
int x,y;
}node[MAXN];
int FIND_PATH(int x){
if(x == set[x]) return x;
return set[x] = FIND_PATH(set[x]);
}
void UNION(int x,int y){
x = FIND_PATH(x);
y = FIND_PATH(y);
if(x == y) return;
if(rank[x] > rank[y]) set[y] = set[x];
else{
set[x] = set[y];
if(rank[x] == rank[y]) rank[y]++;
}
}
int dis(NODE X,NODE Y){
int dx = X.x - Y.x;
int dy = X.y - Y.y;
return (dx * dx + dy * dy);
}
int vis[MAXN];
int main(){
char c;
int n,d,m,p;
cin>>n>>d;
for(int i=1;i<=n;i++) set[i] = i;
for(int i=1;i<=n;i++) cin>>node[i].x>>node[i].y;
while(cin>>c){
if(c == 'O'){
cin>>m;
for(int i=1;i<=n;i++){
if(vis[i]&&i!=m&&dis(node[m],node[i])<=d*d){
UNION(i,m);
}
}
vis[m] = 1;
}else if(c == 'S'){
cin>>m>>p;
if(FIND_PATH(m) == FIND_PATH(p)) cout<<"SUCCESS"<<endl;
else cout<<"FAIL"<<endl;
}
}
return 0;
}
2. poj 1611 The Suspects
#include <iostream>
using namespace std;
const int MAXN = 2e5+100;
int set[MAXN];
int rank[MAXN];
struct NODE{
int x,y;
}node[MAXN];
int FIND_PATH(int x){
if(x == set[x]) return x;
return set[x] = FIND_PATH(set[x]);
}
void UNION(int x,int y){
x = FIND_PATH(x);
y = FIND_PATH(y);
if(x == y) return;
if(rank[x] > rank[y]) set[y] = set[x];
else{
set[x] = set[y];
if(rank[x] == rank[y]) rank[y]++;
}
}
int main(){
int n,m,p,x,y;
while(cin>>n>>m){
if(n == 0&&m == 0) break;
for(int i=0;i<n;i++) set[i] = i;
while(m--){
cin>>p>>x;
for(int i=1;i<p;i++){
cin>>y;
UNION(x,y);
}
}
int ans = 0;
for(int i=0;i<n;i++){
if(FIND_PATH(i) == FIND_PATH(0)) ans++;
}cout<<ans<<endl;
}
return 0;
}
3. hdu 1213 How Many Tables
- 水题
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector<int> s(n + 1);
for(int i=1;i<=n;i++) s[i] = i;
function<int(int)> FIND = [&](int u){
return s[u] == u ? u : s[u] = FIND(s[u]);
};
for(int i=0;i<m;i++){
int u, v;
cin >> u >> v;
u = FIND(s[u]);
v = FIND(s[v]);
s[u] = v;
}
int ans = 0;
for(int i=1;i<=n;i++){
if(i == FIND(i)) ans += 1;
}
cout << ans << '\n';
}
return 0;
}
4. hdu 3038 How Many Answers Are Wrong
给出若干个区间加法关系，让你判断这里面有多少错误
- 此题是带权并查集
-
我们来研究一下权值的更新过程，假设输入
u,
v
,
w
u,v,w
u
,
v
,
w
，先画出下面的图
-
上图表示
uu
u
的祖先节点是
fu
fu
f
u
，
vv
v
的祖先节点是
fv
fv
f
v
，
va
l
val
v
a
l
数组的含义是当前节点相对于祖先节点的权值，如果现在要合并
uu
u
和
vv
v
，那么我们要合并
fu
fu
f
u
和
fv
fv
f
v
，
-
那么假设我们现在以
fv
fv
f
v
为祖先节点进行合并，那么显然两条路径权值应该相等，所以有
va
l
[
u
]
+
v
a
l
[
f
u
]
=
v
a
l
[
v
]
+
w
val[u]+val[fu]=val[v]+w
v
a
l
[
u
]
+
v
a
l
[
f
u
]
=
v
a
l
[
v
]
+
w
，而现在我们要求的是
va
l
[
f
u
]
val[fu]
v
a
l
[
f
u
]
，所以有
va
l
[
f
u
]
=
v
a
l
[
v
]
−
v
a
l
[
u
]
+
w
val[fu]=val[v]-val[u]+w
v
a
l
[
f
u
]
=
v
a
l
[
v
]
−
v
a
l
[
u
]
+
w
-
上面是合并的例子，如果我们现在已经发现
uu
u
和
vv
v
已经处于一个集合，那么有下图
-
注意我们已经进行路径压缩，所以
uu
u
到
fv
fv
f
v
的总长为
va
l
[
u
]
val[u]
v
a
l
[
u
]
，那么此时应该进行验证了，应该有
w+
v
a
l
[
v
]
=
v
a
l
[
u
]
w+val[v]=val[u]
w
+
v
a
l
[
v
]
=
v
a
l
[
u
]
，如果不满足说明出现矛盾
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
while(cin >> n >> m){
vector<int> s(n + 1);
vector<int> val(n + 1);
for(int i=1;i<=n;i++) s[i] = i;
function<int(int)> FIND = [&](int u){
if(u != s[u]){
int fa = s[u];
s[u] = FIND(fa);
val[u] += val[fa];
}
return s[u];
};
int ans = 0;
while(m--){
int u, v, w;
cin >> u >> v >> w;
u -= 1;
int fu = FIND(u);
int fv = FIND(v);
if(fu == fv){
if(val[u] - val[v] != w){
ans += 1;
}
}else{
s[fu] = fv;
val[fu] = w + val[v] - val[u];
}
}
cout << ans << '\n';
}
return 0;
}
5. poj 1182 食物链
- 扩展域并查集
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
const int N = 5e4 + 100;
int st[N * 3];
int FIND(int x){
return x == st[x] ? x : st[x] = FIND(st[x]);
}
void Merge(int x, int y){
int fx = FIND(x);
int fy = FIND(y);
if(fx != fy){
st[fx] = fy;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for(int i=1;i<=3*n;i++){
st[i] = i;
}
int ans = 0;
for(int i=0;i<k;i++){
int d, x, y;
cin >> d >> x >> y;
if(x > n || y > n){
ans += 1;
continue;
}
if(x == y && d == 2){
ans += 1;
continue;
}
if(d == 1){
if(FIND(x) == FIND(y + n) || FIND(x) == FIND(y + 2 * n)){
ans += 1;
continue;
}
Merge(x, y);
Merge(x + n, y + n);
Merge(x + 2 * n, y + 2 * n);
}else{
if(FIND(x) == FIND(y) || FIND(x) == FIND(y + 2 * n)){
ans += 1;
continue;
}
Merge(x, y + n);
Merge(x + n, y + 2 * n);
Merge(x + 2 * n, y);
}
}
cout << ans << '\n';
return 0;
}
6. poj 1417 True Liars
- 带权并查集+dp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
using namespace std;
const int N = 700;
int fa[N], val[N];
int dp[N][N]; // dp[i][j]表示存储到第i个集合, 选择种类和为j的方法数
int path[N][N];
int vis[N][2];
int FIND(int x){
if(x != fa[x]){
int root = FIND(fa[x]);
val[x] ^= val[fa[x]];
fa[x] = root;
}
return fa[x];
}
void Merge(int u, int v, int d){
int fu = FIND(u);
int fv = FIND(v);
if(fu != fv){
fa[fv] = fu;
val[fv] = val[u] ^ val[v] ^ d;
}
}
int g[N];
int tag[N][2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, p1, p2;
while(cin >> n >> p1 >> p2){
if(n + p1 + p2 == 0) break;
for(int i=1;i<=p1+p2;i++) fa[i] = i;
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);
memset(path, 0, sizeof path);
memset(val, 0, sizeof val);
memset(tag, 0, sizeof tag);
memset(g, 0, sizeof g);
for(int i=0;i<n;i++){
int u, v;
string s;
cin >> u >> v >> s;
if(s[0] == 'y'){
Merge(u, v, 0);
}else{
Merge(u, v, 1);
}
}
int cnt = 0;
for(int i=1;i<=p1+p2;i++){
if(i == FIND(i)) g[i] = ++cnt;
}
for(int i=1;i<=p1+p2;i++){
tag[g[FIND(i)]][val[i]] += 1;
}
dp[0][0] = 1;
for(int i=1;i<=cnt;i++){
for(int j=0;j<=p1+p2;j++){
if(j - tag[i][0] >= 0 && dp[i - 1][j - tag[i][0]]){
dp[i][j] += dp[i - 1][j - tag[i][0]];
path[i][j] = tag[i][0];
}
if(j - tag[i][1] >= 0 && dp[i - 1][j - tag[i][1]]){
dp[i][j] += dp[i - 1][j - tag[i][1]];
path[i][j] = tag[i][1];
}
}
}
if(dp[cnt][p1] != 1){
cout << "no\n";
}else{
for(int i=cnt,j=p1;j>0&&i>0;i--){
if(path[i][j] == tag[i][0]){
vis[i][0] = 1;
}else{
vis[i][1] = 1;
}
j -= path[i][j];
}
for(int i=1;i<=p1+p2;i++){
if(vis[g[FIND(i)]][val[i]]){
cout << i << '\n';
}
}
cout << "end\n";
}
}
return 0;
}
7. poj 1456 Supermarket
- 贪心，把商品按照价格降序排列，逆序枚举每一天，看能否购买即可
- 正确性证明，因为卖货全都是一天时间，卖个贵的显然要优于卖个便宜的，且可以等价替换
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
using namespace std;
struct st{
int p, d;
bool operator < (const st &B)const{
return p > B.p || (p == B.p && d > B.d);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
while(cin >> n){
vector<st> vs(n);
int mx = -1;
for(int i=0;i<n;i++){
cin >> vs[i].p >> vs[i].d;
mx = max(mx, vs[i].p);
}sort(vs.begin(), vs.end());
vector<int> vis(mx + 1);
int ans = 0;
for(int i=0;i<n;i++){
for(int j=vs[i].d;j>0;j--){
if(!vis[j]){
ans += vs[i].p;
vis[j] = 1;
break;
}
}
}
cout << ans << '\n';
}
return 0;
}
8. poj 1733 Parity game
-
如果区间
[u
,
v
]
[u,v]
[
u
,
v
]
内部有偶数个1，那么不妨设
va
l
[
v
]
−
v
a
l
[
u
−
1
]
=
0
val[v]-val[u-1]=0
v
a
l
[
v
]
−
v
a
l
[
u
−
1
]
=
0
，如果内部有奇数个1，那么
va
l
[
v
]
−
v
a
l
[
u
−
1
]
=
1
val[v]-val[u-1]=1
v
a
l
[
v
]
−
v
a
l
[
u
−
1
]
=
1
，那么显然是一个带权并查集，更新权值的过程中采用异或代替取模操作
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
using namespace std;
map<int, int> mp, val;
int FIND(int x){
if(x == mp[x]) return x;
if(x != mp[x]){
int root = FIND(mp[x]);
val[x] ^= val[mp[x]];
mp[x] = root;
}
return mp[x];
}
void Merge(int u, int v, int d){
int fu = FIND(u);
int fv = FIND(v);
if(fu != fv){
val[fu] = val[u] ^ d ^ val[v];
mp[fu] = fv;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(m), b(m), c(m);
for(int i=0;i<m;i++){
cin >> a[i] >> b[i];
a[i] -= 1;
mp[a[i]] = a[i];
mp[b[i]] = b[i];
string s;
cin >> s;
if(s[0] == 'e') c[i] = 0;
else c[i] = 1;
}
int ans = 0;
for(int i=0;i<m;i++){
if(FIND(a[i]) != FIND(b[i])){
Merge(a[i], b[i], c[i]);
}else{
if(val[a[i]] ^ val[b[i]] != c[i]) break;
}
ans += 1;
}
cout << ans;
return 0;
}
9. poj1984 Navigation Nightmare
- 显然是两个方向上的带权并查集即可，注意两个方向完全独立
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
typedef long long ll;
using namespace std;
ll ABS(ll x){
return x < 0 ? -x : x;
}
const int N = 4e4 + 10;
int fax[N], fay[N];
ll xx[N], yy[N];
int FINDx(int x){
if(x == fax[x]) return x;
int root = FINDx(fax[x]);
xx[x] += xx[fax[x]];
return fax[x] = root;
}
int FINDy(int x){
if(x == fay[x]) return x;
int root = FINDy(fay[x]);
yy[x] += yy[fay[x]];
return fay[x] = root;
}
void Mergex(int u, int v, int d){
int fu = FINDx(u);
int fv = FINDx(v);
if(fu != fv){
xx[fu] = xx[v] + d - xx[u];
fax[fu] = fv;
}
}
void Mergey(int u, int v, int d){
int fu = FINDy(u);
int fv = FINDy(v);
if(fu != fv){
yy[fu] = yy[v] + d - yy[u];
fay[fu] = fv;
}
}
struct st{
int id;
int u, v;
ll dis;
char c;
};
struct ask{
int u, v;
int number;
int id;
bool operator < (const ask &B)const{
return number < B.number;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for(int i=1;i<=n;i++){
fax[i] = i;
fay[i] = i;
}
vector<st> vs(m);
for(int i=0;i<m;i++){
cin >> vs[i].u >> vs[i].v >> vs[i].dis >> vs[i].c;
if(vs[i].u > vs[i].v){
swap(vs[i].u, vs[i].v);
if(vs[i].c == 'E') vs[i].c = 'W';
else if(vs[i].c == 'W') vs[i].c = 'E';
else if(vs[i].c == 'N') vs[i].c = 'S';
else if(vs[i].c == 'S') vs[i].c = 'N';
}
vs[i].id = i;
}
int q;
cin >> q;
vector<ask> que(q);
for(int i=0;i<q;i++){
cin >> que[i].u >> que[i].v >> que[i].number;
que[i].id = i;
}sort(que.begin(), que.end());
int now = 0;
vector<ll> ans(q);
for(int i=0;i<q;i++){
while(now < que[i].number){
if(vs[now].c == 'E'){
Mergex(vs[now].u, vs[now].v, vs[now].dis);
Mergey(vs[now].u, vs[now].v, 0);
}
if(vs[now].c == 'W'){
Mergex(vs[now].u, vs[now].v, -vs[now].dis);
Mergey(vs[now].u, vs[now].v, 0);
}
if(vs[now].c == 'N'){
Mergey(vs[now].u, vs[now].v, vs[now].dis);
Mergex(vs[now].u, vs[now].v, 0);
}
if(vs[now].c == 'S'){
Mergey(vs[now].u, vs[now].v, -vs[now].dis);
Mergex(vs[now].u, vs[now].v, 0);
}
now += 1;
}
if(FINDx(que[i].u) == FINDx(que[i].v) && FINDy(que[i].u) == FINDy(que[i].v)){
ans[que[i].id] = ABS(xx[que[i].u] - xx[que[i].v]) + ABS(yy[que[i].u] - yy[que[i].v]);
}else{
ans[que[i].id] = -1;
}
}
for(int i=0;i<q;i++){
cout << ans[i] << '\n';
}
return 0;
}
10. poj 2912 A Bug’s Life
-
[u
,
v
]
[u,v]
[
u
,
v
]
表示异性，问是否矛盾 - 和食物链那题类似，只不过种类数变少了， 也可使用扩展域并查集，这里使用带权并查集，用权值表示属于哪一类
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
using namespace std;
const int N = 3e3;
int s[N];
int val[N];
int FIND(int x){
if(x == s[x]) return x;
int root = FIND(s[x]);
val[x] ^= val[s[x]];
return s[x] = root;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for(int kase=1;kase <= t;kase++){
int n, m;
cin >> n >> m;
for(int j=1;j<=n;j++){
s[j] = j;
val[j] = 0;
}
bool ok = true;
cout << "Scenario #" << kase << ":\n";
for(int j=0;j<m;j++){
int u, v;
cin >> u >> v;
int fu = FIND(u);
int fv = FIND(v);
if(fu != fv){
s[fu] = fv;
val[fu] = val[u] ^ val[v] ^ 1;
}else{
if(val[u] == val[v]) ok = false;
}
}
if(ok) cout << "No suspicious bugs found!\n";
else cout << "Suspicious bugs found!\n";
cout << '\n';
}
return 0;
}
11. poj 2912 Rochambeau
- 枚举每一个人可能成为裁判的情况
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
using namespace std;
struct st{
int u, v;
char c;
};
const int N = 505;
int fa[N], val[N];
int FIND(int x){
if(x == fa[x]) return x;
int root = FIND(fa[x]);
val[x] = (val[x] + val[fa[x]]) % 3;
return fa[x] = root;
}
bool Merge(int u, int v, int d){
int fu = FIND(u);
int fv = FIND(v);
if(fu != fv){
val[fv] = (val[u] + d + 3 - val[v]) % 3;
fa[fv] = fu;
}else{
if((val[v] - val[u] + 3) % 3 != d) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
while(cin >> n >> m){
int u, v;
char c;
vector<st> vs(m);
for(int i=0;i<m;i++){
cin >> vs[i].u >> vs[i].c >> vs[i].v;
}
int ans = 0;
bool ok = true;
int tot = 0;
int line = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
fa[j] = j;
val[j] = 0;
}
ok = true;
for(int j=0;j<m;j++){
int d = 0;
if(vs[j].u == i || vs[j].v == i) continue;
if(vs[j].c == '=') d = 0;
if(vs[j].c == '>') d = 1;
if(vs[j].c == '<') d = 2;
if(!Merge(vs[j].u, vs[j].v, d)){
ok = false;
line = max(line, j + 1);
break;
}
}
if(ok){
tot += 1;
ans = i;
}
}
if(tot > 1){
cout << "Can not determine\n";
}else if(!tot){
cout << "Impossible\n";
}else{
cout << "Player " << ans << " can be determined to be the judge after " << line << " lines\n";
}
}
return 0;
}
12. ZOJ-3261 Connections in Galaxy War
- 离线倒着处理？以前做的好像挺常规的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
int fa[N], val[N], p[N];
int FIND(int x){
if(x == fa[x]) return x;
int root = FIND(fa[x]);
val[x] = max(val[x], val[fa[x]]);
return fa[x] = root;
}
void Merge(int u, int v){
int fu = FIND(u);
int fv = FIND(v);
if(fu != fv){
if(val[fu] == val[fv]){
if(fu > fv) swap(fu, fv);
fa[fv] = fu;
}else if(val[fu] > val[fv]){
fa[fv] = fu;
}else{
fa[fu] = fv;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
bool f = false;
while(cin >> n){
if(f) cout << '\n';
f = true;
for(int i=0;i<n;i++){
cin >> p[i];
val[i] = p[i];
fa[i] = i;
}
int m;
cin >> m;
vector<pair<int, int> > vs(m);
for(int i=0;i<m;i++){
cin >> vs[i].first >> vs[i].second;
if(vs[i].first > vs[i].second) swap(vs[i].first, vs[i].second);
}
int q;
cin >> q;
vector<vector<int> > operation(q);
set<pair<int, int> > st;
for(int i=0;i<q;i++){
string s;
int u, v;
cin >> s;
if(s == "query"){
cin >> u;
operation[i].push_back(u);
}else{
cin >> u >> v;
if(u > v) swap(u, v);
operation[i].push_back(u);
operation[i].push_back(v);
st.insert(make_pair(u, v));
}
}
for(int i=0;i<m;i++){
if(!st.count({vs[i].first, vs[i].second})){
Merge(vs[i].first, vs[i].second);
}
}
vector<int> ans;
for(int i=q-1;i>=0;i--){
if((int)operation[i].size() > 1){
int u = operation[i][0];
int v = operation[i][1];
Merge(u, v);
}else{
int root = FIND(operation[i][0]);
if(val[root] > p[operation[i][0]]){
ans.push_back(root);
}else{
ans.push_back(-1);
}
}
}
reverse(ans.begin(), ans.end());
for(auto i : ans){
cout << i << '\n';
}
}
return 0;
}
13. hdu 1272 小希的迷宫
- 注意要求输出的是权值最大，编号最小的，所以带权并查集维护的祖先节点应该满足这两条，然后常规思路离线处理即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 100;
int fa[N], val[N], p[N];
int FIND(int x){
if(x == fa[x]) return x;
int root = FIND(fa[x]);
val[x] = max(val[x], val[fa[x]]);
return fa[x] = root;
}
void Merge(int u, int v){
int fu = FIND(u);
int fv = FIND(v);
if(fu != fv){
if(val[fu] == val[fv]){
if(fu > fv) swap(fu, fv);
fa[fv] = fu;
}else if(val[fu] > val[fv]){
fa[fv] = fu;
}else{
fa[fu] = fv;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
bool f = false;
while(cin >> n){
if(f) cout << '\n';
f = true;
for(int i=0;i<n;i++){
cin >> p[i];
val[i] = p[i];
fa[i] = i;
}
int m;
cin >> m;
vector<pair<int, int> > vs(m);
for(int i=0;i<m;i++){
cin >> vs[i].first >> vs[i].second;
if(vs[i].first > vs[i].second) swap(vs[i].first, vs[i].second);
}
int q;
cin >> q;
vector<vector<int> > operation(q);
set<pair<int, int> > st;
for(int i=0;i<q;i++){
string s;
int u, v;
cin >> s;
if(s == "query"){
cin >> u;
operation[i].push_back(u);
}else{
cin >> u >> v;
if(u > v) swap(u, v);
operation[i].push_back(u);
operation[i].push_back(v);
st.insert(make_pair(u, v));
}
}
for(int i=0;i<m;i++){
if(!st.count({vs[i].first, vs[i].second})){
Merge(vs[i].first, vs[i].second);
}
}
vector<int> ans;
for(int i=q-1;i>=0;i--){
if((int)operation[i].size() > 1){
int u = operation[i][0];
int v = operation[i][1];
Merge(u, v);
}else{
int root = FIND(operation[i][0]);
if(val[root] > p[operation[i][0]]){
ans.push_back(root);
}else{
ans.push_back(-1);
}
}
}
reverse(ans.begin(), ans.end());
for(auto i : ans){
cout << i << '\n';
}
}
return 0;
}
14. poj 1308 Is It A Tree?
- 如果输入的点不能构成一个连通块，或者连边之后出现环就说明不是树
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <stack>
using namespace std;
const int N = 2e5 + 5;
int s[N + 20];
int FIND(int x){
return x == s[x] ? x : s[x] = FIND(s[x]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int u, v;
vector<int> vs;
for(int i=1;i<=N;i++) s[i] = i;
int mx = 0;
int kase = 1;
bool yes = true;
while(cin >> u >> v){
if(u == -1 && v == -1) break;
mx = max(max(u, v), mx);
while(true){
if(u == 0 && v == 0){
sort(vs.begin(), vs.end());
vs.erase(unique(vs.begin(), vs.end()), vs.end());
for(int i=1;i<(int)vs.size();i++){
if(FIND(vs[i]) != FIND(vs[i - 1])) yes = false;
}
if(yes){
cout << "Case " << kase << " is a tree.\n";
}else{
cout << "Case " << kase << " is not a tree.\n";
}
for(int i=1;i<=mx;i++) s[i] = i;
kase += 1;
mx = 0;
yes = true;
vs.clear();
break;
}
vs.push_back(u);
vs.push_back(v);
mx = max(mx, max(u, v));
int fu = FIND(u);
int fv = FIND(v);
if(fu == fv) yes = false;
s[fu] = fv;
cin >> u >> v;
}
}
return 0;
}
版权声明：本文为roadtohacker原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。