并查集—河工oj

1304-连通块中点的个数

P1304 - 连通块中点的个数 - HAUEOJ

代码（用了关流不能用puts输出yes和no，会出错）

#include<bits/stdc++.h>
using namespace std;//连通块—并查集int n, m;
const int N = 1e5+10;
int p[N], cnt[N];void init() {for(int i = 1; i < N; i ++) p[i] = i, cnt[i] = 1;
} int find(int x) {if(p[x]!=x) p[x] = find(p[x]);return p[x];
}int main() {init();ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);//init();cin >> n >> m;while(m --) {string op;cin >> op;int a, b;if(op=="C") {cin >> a >> b;int pa = find(a), pb = find(b);if(pa==pb) continue;p[pa] = pb;cnt[pb] += cnt[pa];}else if(op=="Q2"){cin >> a;//int pa = find(a);//puts("1111111");cout << cnt[find(a)] << endl;}       else if(op=="Q1") {cin >> a >> b;int pa = find(a), pb = find(b);if(pa == pb) cout << "Yes" << endl;else cout << "No" << endl;}
//      else if(op=="Q2"){
//          cin >> a;
//          //int pa = find(a);
//          cout << cnt[find(a)] << endl;
//      }//op.clear();}return 0;
}

1306-关押罪犯

P1306 - 关押罪犯 - HAUEOJ

分析

b用于索引矛盾罪犯，来实现集合分离。

代码

#include<bits/stdc++.h>
using namespace std;// 两集合，并查集，集合合并 
int n, m;
const int N = 1e5+10;
int p[N], b[N]; struct crr {int x, y;int r;bool operator < (const crr &W) const {return r > W.r;}
}c[N];int find(int x) {if(x!=p[x]) p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;for(int i = 1; i <= m; i ++) {int x, y, r;cin >> x >> y >> r;c[i].x = x, c[i].y = y, c[i].r = r;}sort(c+1,c+1+m);for(int i = 1; i <= n; i ++) p[i] = i;int maxx = 0;for(int i = 1; i <= m; i ++) {// 在一个监狱中的最大的边 if(find(c[i].x)==find(c[i].y)) {maxx = c[i].r;break;}if(!b[c[i].x]) b[c[i].x] = c[i].y;else {int _a = find(b[c[i].x]), _b = find(c[i].y);p[_a] = _b;} if(!b[c[i].y]) b[c[i].y] = c[i].x;else {int _a = find(b[c[i].y]), _b = find(c[i].x);p[_a] = _b;}}cout << maxx << endl;return 0;
}