atcoder ABC49 D問題

Union-Find木を使わないと解けない問題だったので、解法をメモ

問題は、グラフを２通り作り両方において、ある辺とある辺が連結している個数を求める問題である。はじめは深さ優先探索をしていたが頂点の個数が多いのでMLEやTLEを起こしてしまうので、Union-Find木で連結の判定をしなければならない。Union-Find木の基本的な実装は下の通り。

class UnionFind{
    int[] parent;        //親ノード
    public UnionFind(int N){
        this.parent = new int[N];       //初期化
        for(int i = 0; i < N;i++){
            parent[i] = i;
        }
    }
    public int root(int x){         //根要素を取得
        if(parent[x] == x){         //初期状態
            return x;
        }else{
            return parent[x] = root(parent[x]);     //再帰によって根を取得
        }
    }
    public void unite(int x,int y){     //統合メソッド
        if(same(x,y)){                  //同じ根なら終了
            return;
        }
        int xroot = root(x);
        int yroot = root(y);
        parent[xroot] = yroot;          //統合
        return;

    }

    public boolean same(int x,int y){           //根が同じか（同じグループに属しているか）を判定
        return(root(x) == root(y));
    }
}