并查集—河工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;
}