1703-Fine them, Catch them

問題（外部リンク）

1703 -- Find them, Catch them

実装の概要

グループ分けの問題で、Union-Find木が非常に有効です。ですが、所属している組織でグループ分けをしようとするとうまく行きません。
そこで今回はA, Bという事実がそれぞれ共存するなら同じグループと考えます。
例えば、問題の実行例にあるように「D 1 2」と入力されたとします。このとき、「1がドラゴンに所属」と「2がスネークに所属」という2つの事実は共存できるので同じグループです。同時に、「1がスネークに所属」と「2がドラゴンに所属」という2つの事実もこれはこれで共存できるので同じグループです。そのため両方の可能性を考えそれぞれ別個にunionします。
情報が揃うまではunionが必要なだけ行われていないのでNot sure yet.と出力され、十分に情報が揃えば同じグループか異なるグループかを決定できます。
なお、N人についてそれぞれスネークまたはドラゴンに所属という2つの可能性を考えるため、Union-Find木の要素数は2*Nとなることに注意してください。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		String[] tmpArray ;
		for(int i = 0; i < t; i++){
			System.gc();

			tmpArray = br.readLine().split(" ");
			int n = Integer.parseInt(tmpArray[0]);
			int m = Integer.parseInt(tmpArray[1]);

			solve(n, m, br);

		}
	}

	static void solve(int n, int m, BufferedReader br) throws IOException{

		//前半をドラゴン、後半をスネークに割り振る
		DisjointSet set = new DisjointSet(2*n);

		String[] tmpArray;
		for(int i = 0; i < m; i++){
			tmpArray = br.readLine().split(" ");

			int gang1 = Integer.parseInt(tmpArray[1]);
			int gang2 = Integer.parseInt(tmpArray[2]);

			if(tmpArray[0].equals("A")){
				if(set.isSameSet(gang1, gang2)){
					System.out.println("In the same gang.");
				}
				else if(set.isSameSet(gang1, gang2+n) ){
					System.out.println("In different gangs.");
				}
				else {
					System.out.println("Not sure yet.");
				}
			}
			else {
				set.union(gang1, gang2+n);
				set.union(gang1 + n, gang2);
			}
		}

		System.gc();
	}

}

class DisjointSet {
    private int n;
    private int[] p;
    private int[] rank;

    public DisjointSet(int n){
        this.n = n;

        p = new int[n + 1];
        rank = new int[n + 1];

        for(int i = 1; i <= n; i++){
            makeSet(i);
        }
    }

    private void makeSet(int x){
        p[x] = x;
        rank[x] = 0;
    }

    public void union(int x, int y){
        link (findSet(x), findSet(y));
    }

    private int findSet(int x){
        if(x != p[x]){
            p[x] = findSet( p[x]);
        }
        return p[x];
    }

    public boolean isSameSet(int x, int y){
        return findSet(x) == findSet(y);
    }

    private void link(int x, int y){
        if(rank[x] > rank[y]){
            p[y] = x;
        }
        else {
            p[x] = y;
            if(rank[x] == rank[y]){
                rank[y]++;
            }
        }
    }
}