并查集写挂了?求助
查看原帖
并查集写挂了?求助
245391
Chris_pan楼主2021/11/4 21:27
#include <bits/stdc++.h>
using namespace std;

const int N = 30000 + 10;

int T;
int fa[N],rnk[N],ans[N];

void init(int n){
	for (int i = 1;i <= n;i++) {
		fa[i] = i;
		rnk[i] = 0;
		ans[i] = 1;
	}
}

int find(int x){
	if (fa[x] == x) return x;
	int u = fa[x];
	fa[x] = find(fa[x]);
	rnk[x] += rnk[u];
	ans[x] = ans[fa[x]];
	return fa[x];
}

void unite(int x,int y){
	x = find(x),y = find(y);
	fa[x] = y;
	rnk[x] += ans[y];
	ans[x] += ans[y];
	ans[y] = ans[x];
}

bool same(int x,int y){
	return find(x) == find(y);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	init(30000);
	cin >> T;
	while (T--){
		char c;cin >> c;
		if (c == 'M') {
			int i,j;cin >> i >> j;
			unite(i,j);
		} else {
			int i,j;cin >> i >> j;
			if (!same(i,j)) {
				cout << -1 << endl;
				return 0;
			} 
            cout << abs(rnk[i] - rnk[j]) - 1 << endl;
		}
	}
	return 0;
}
2021/11/4 21:27
加载中...