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