Union-Find: Merging Groups

Clubs that merge

Students start alone. Then announcements arrive: “A and B's groups merge.” At any moment someone asks: “Are X and Y in the same group?” Re-running DFS after every merge is slow. Union-find answers in almost O(1).

Every group has a leader

Each person points to a parent. Follow the parents up and you reach the group's leader (someone who is their own parent). Two people are in the same group if they have the same leader. To merge, make one leader point to the other:

public class Main {
    static int[] parent;

    static int find(int x) {                       // who is x's leader?
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression: point straight at the leader
        return parent[x];
    }

    static boolean union(int a, int b) {           // merge the two groups
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                // already together
        parent[ra] = rb;
        return true;
    }

    public static void main(String[] args) {
        int n = 6;
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;    // everyone leads their own group

        union(1, 2);
        union(3, 4);
        union(2, 4);
        System.out.println("1 and 3 together? " + (find(1) == find(3)));
        System.out.println("1 and 5 together? " + (find(1) == find(5)));
        System.out.println("merge 1 and 4 again: " + union(1, 4));
    }
}

Output

1 and 3 together? true
1 and 5 together? false
merge 1 and 4 again: false

The line parent[x] = find(parent[x]) is path compression: after one search, everyone on the path points straight at the leader, so future searches are nearly instant.

Think of it like this: After asking around once to find out who the club captain is, you write the captain's name down so you never have to ask the chain again.