Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Disjoint Set: Union Find Tree"
https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A
・互いに素な集合
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DSL_1_A : Disjoint Set: Union Find Tree
/* Aizu Online Judge in C++ #DSL_1_A : Disjoint Set: Union Find Tree https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; const int num=10001; int arr[num]; int find(int a){ if(a==arr[a]){ return a; } return find(arr[a]); } void unite(int a,int b){ int fa=find(a); int fb=find(b); if(fa==fb){ return; }else if(fa<fb){ arr[fb]=arr[fa]; }else{ arr[fa]=arr[fb]; } } int main(void){ for(int i=0;i<num;i++){ arr[i]=i; } int n,q; cin>>n>>q; for(int i=0;i<q;i++){ int c,x,y; cin>>c>>x>>y; if(c==0){ unite(x,y); }else{ cout<<(find(x)==find(y))<<endl; } } return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/