読者です 読者をやめる 読者になる 読者になる

union_findの実装

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

class union_find{
private:
	int *par;
	int *rank;
	int size;
public:	
	union_find(int n){
		par = new int[n];
		rank = new int[n];
		size = n;
		for(int i=0; i<n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x){
		if(par[x]==x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x==y) return;

		if(rank[x] < rank[y]){
			par[x]=y;
		}else{
			par[y]=x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

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

	void print(){
		vector <int> t_unit(size);

		int count=0;

		for(int i=0; i<size; i++){
			if(t_unit[i]==0){
				cout << "group " << count++ << endl;
				t_unit[i]=1;
			}else{
				continue;
			}
			for(int j=i; j<size; j++){
				if(same(i,j)){
					cout << j << " ";
					t_unit[j]=1;
				}
			}
			cout << endl;

		}
	}
};

int main(void){
	union_find uf(10);

	uf.print();
	cout << "unite: 0-1" << endl;
	uf.unite(0,1);
	uf.print();
	cout << "unite: 2-3" << endl;
	uf.unite(2,3);
	uf.print();
	cout << "unite: 1-2" << endl;
	uf.unite(1,2);
	uf.print();
	return 0;
}

出力結果

group 0
0 
group 1
1 
group 2
2 
group 3
3 
group 4
4 
group 5
5 
group 6
6 
group 7
7 
group 8
8 
group 9
9 
unite: 0-1
group 0
0 1 
group 1
2 
group 2
3 
group 3
4 
group 4
5 
group 5
6 
group 6
7 
group 7
8 
group 8
9 
unite: 2-3
group 0
0 1 
group 1
2 3 
group 2
4 
group 3
5 
group 4
6 
group 5
7 
group 6
8 
group 7
9 
unite: 1-2
group 0
0 1 2 3 
group 1
4 
group 2
5 
group 3
6 
group 4
7 
group 5
8 
group 6
9