寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #DSL_1_A : Disjoint Set: Union Find Tree

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/