Find them, Catch them

A tyical uses of union find. To solve this type of problem, we have two different approach. One is re-encode the relationships. Let's say we have two class A and B, once given two people a and b can not be in the same class, that means either a in A and b in B and b in A and a in B is true. We use a-A, a-B, b-A and b-B to stands for each containing states. Then if two states should appears at the same time, we union them in union find set. For a people numbered i and total people count N, we use 0 ~ N - 1 to stands for i-A, N ~ 2N - 1 to stands for i-B, then we can query relationship or union two state easily. This solution is easily to understand and implment and applys to multiple classes questions. Also this solution is not vulnerable to StackOverflowError. But it will cost more spaces.

import java.io.*;
import java.util.*;

public class FindThemCatchThem {
    static int[] ids;
    static int[] rank;

    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); 
        int t = Integer.parseInt(buf.readLine());

        for (int i = 0; i < t; i++) {
            String str[] = buf.readLine().split(" ");  
            int n = Integer.parseInt(str[0]);  
            int m = Integer.parseInt(str[1]);

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

            for (int j = 0; j < ids.length; j++) {
                ids[j] = j;
            }

            for (int j = 0; j < m; j++) {
                str = buf.readLine().split(" ");  
                String op = str[0];
                int a = Integer.parseInt(str[1]);  
                int b = Integer.parseInt(str[2]);

                if (op.equals("D")) {
                    union(a, b);
                } else {
                    if(n == 2)  
                        System.out.println("In different gangs.");  
                    else if(find(a)==find(b)){  
                        if(rank[a] == rank[b])  
                            System.out.println("In the same gang.");  
                        else  
                            System.out.println("In different gangs.");  
                    }else  
                        System.out.println("Not sure yet."); 
                }
            }
        }
    }

    private static void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);

        ids[pid] = qid;
        rank[pid] = (rank[p] + rank[q] + 1) % 2;
    }

    private static int find(int p) {
        if (ids[p] == p) return p;

        int root = find(ids[p]);
        rank[p] = (rank[p] + rank[ids[p]]) % 2;
        return ids[p] = root;
    }
}

Another solution is that we uses rank values to mark if current node is in the same class of it's parent node. If it is the same, we use 0, or we use 1. Then when we are peforming find and union operation, we should handle and update the rank values correctly. In this implementation, we have to use recursive way to perform find operation and after find we point current node directly to its final root. The new rank is decided by current rank and it's old parent's new rank. As after the recursion, currently the parent node is directly point to root. So parent node p, root node rt and current node c has the following relationships:

1. p and rt in same clas, c and p in same class, then c and rt in same class
2. p and rt not in same clas, c and p not in same class, then c and rt in same class
3. Otherwise, c and rt not in same class

The relationships above can be represented with a consice expression: (rank[c] + rank[p]) % 2.

Also, when perform union, we have to handle similar things too. Let p and q be two roots of two elements to union, the corresponding expression will be (rank[p] + rank[q] + 1) % 2. This solution is a little hard to understand and not easy to be implemented right, it is also vulnerable to StackOverflow. But this solution can be inducted to muliple classes questions and also more save in space.

import java.io.*;
import java.util.*;

public class FindThemCatchThem2 {
    static int[] ids;
    static int[] sizes;

    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); 
        int t = Integer.parseInt(buf.readLine());

        for (int i = 0; i < t; i++) {
            String str[] = buf.readLine().split(" ");  
            int n = Integer.parseInt(str[0]);  
            int m = Integer.parseInt(str[1]);

            ids = new int[n * 2];
            sizes = new int[n * 2];

            for (int j = 0; j < ids.length; j++) {
                ids[j] = j;
                sizes[i] = 1;
            }

            for (int j = 0; j < m; j++) {
                str = buf.readLine().split(" ");  
                String op = str[0];
                int a = Integer.parseInt(str[1]) - 1;
                int b = Integer.parseInt(str[2]) - 1;

                if (op.equals("D")) {
                    union(a, b + n);
                    union(a + n, b);
                } else {
                    if(connected(a, b))  
                        System.out.println("In the same gang.");  
                    else if(connected(a, b + n)){  
                        System.out.println("In different gangs.");  
                    }else  
                        System.out.println("Not sure yet."); 
                }
            }
        }
    }

    private static void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);

        if (sizes[pid] < sizes[qid]) {
            ids[pid] = qid;
            sizes[qid] += sizes[pid];
        } else {
            ids[qid] = pid;
            sizes[pid] += sizes[qid];
        }
    }

    private static int find(int p) {
        while (p != ids[p]) {
            ids[p] = ids[ids[p]];
            p = ids[p];
        }
        return p;
    }

    private static boolean connected(int p, int q) {
        return find(p) == find(q);
    }
}