并查集题目合集

#include<bits/stdc++.h> 
using namespace std;
int bin[1010];
int findx(int x){
	int r=x;
	while(bin[r]!=r){
		r=bin[r];
	}
	return r;
}
void merge(int x, int y){
	int fx=findx(x), fy=findx(y);
	if(fx!=fy) bin[fx]=fy;
}
int main() {
	int x, y, n, m;
	while(cin>>n, n){
    	cin>>m;
    	int num=0;
		for(int i=1; i<=n; i++){
			bin[i]=i;
		}
		while(m--){
			cin>>x>>y;
			merge(x, y);
		}
		for(int i=1; i<=n; i++){
			if(bin[i]==i) num++;
		}
		cout<<num-1<<endl;
	}return 0;
}

#include<bits/stdc++.h>
using namespace std;
int bin[1010];
int findx(int x){
	int r=x;
	while(r!=bin[r]){
		r=bin[r];
	}
	return r;
}
void merge(int x, int y){
	int fx=findx(x), fy=findx(y);
	if(fx!=fy){
		bin[fx]=fy;
	}
}
int main()
{
    int t;
    cin>>t;
	while(t--){
		int n, m, a, b;
		cin>>n>>m;
		for(int i=1; i<=n; i++){
			bin[i]=i;
		}
		while(m--)
		{
			cin>>a>>b;
			merge(a, b);
		}
		int num=0;
		for(int i=1; i<=n; i++){
			if(bin[i]==i) num++;
		}
		cout<<num<<endl;
	}
    return 0;
}