Union Find

Data structure to store non-overlapping sets

Notes based on William Fiset’s tutorials

To perform Union(E, L)
- If FindRoot(E) == FindRoot(L), do nothing since already same group
- Else Merge(E, L)
To perform FindRoot(E)
- Move up graph until reach root e.g. E > D > C > B > A > F (root!)
- Also do path compression along the way so graph is flat e.g. 
  E > F, D > F, C > F, B > F, A > F
** Path compression will result in amortized O(n) find time since we don't have to keep traversing the graph
To perform Merge(E, L)
- Point root of smaller group to root of larger group e.g. G > F

Sample application of Union Find

Given a graph, create a tree that connects all nodes with the smallest edge values.
1. Sort edge values in ascending order
2. Perform union-find in that order
NodeSize      A1 B1 C1 D1 E1 F1 G1 H1 I1 J1
Root          A  B  C  D  E  F  G  H  I  J
.......................................
Union I, J (update J root)
NodeSize      A1 B1 C1 D1 E1 F1 G1 H1 I2*J1
Root          A  B  C  D  E  F  G  H  I  I*
.......................................
Union A, E (update E root)
NodeSize      A2*B1 C1 D1 E1 F1 G1 H1 I2 J1
Root          A  B  C  D  A* F  G  H  I  I
.......................................
Union C, I (C group size is smaller, update C)
NodeSize      A2 B1 C1 D1 E1 F1 G1 H1 I3*J1
Root          A  B  I* D  A  F  G  H  I  I
.......................................
Union E, F (root of E is A, F group is smaller, update F)
NodeSize      A3 B1 C1 D1 E1 F1 G1 H1 I3 J1
Root          A  B  I  D  A  A* G  H  I  I
.......................................
Union G, H (update H)
NodeSize      A3 B1 C1 D1 E1 F1 G2*H1 I3 J1
Root          A  B  I  D  A  A  G  G* I  I
.......................................
Union B, D (update D)
NodeSize      A3 B2*C1 D1 E1 F1 G2 H1 I3 J1
Root          A  B  I  B* A  A  G  G  I  I
.......................................
Union C, J (root of C and J are I, do nothing)
NodeSize      A3 B2 C1 D1 E1 F1 G2 H1 I3 J1
Root          A  B  I  B  A  A  G  G  I  I
.......................................
Union D, E (root of D is B, root of E is A, group A is bigger.          
            Update B to point to A as root)
NodeSize      A5*B2 C1 D1 E1 F1 G2 H1 I3 J1
Root          A  A* I  B  A  A  G  G  I  I
.......................................
Union D, H (root of D is A, compress. root of H is G.
            Update G to point to A as root)
NodeSize      A7*B2 C1 D1 E1 F1 G2 H1 I3 J1
Root          A  A  I  A* A  A  A* G  I  I
.......................................
Union A, D (same root, do nothing)
NodeSize      A7 B2 C1 D1 E1 F1 G2 H1 I3 J1
Root          A  A  I  A  A  A  A  G  I  I
.......................................
Union B, C (root of C is I. Update I to point to A)
NodeSize      A10*B2 C1 D1 E1 F1 G2 H1 I3 J1
Root          A   A  I  A  A  A  A  G  A* I
Done! Group A now has all nodes

LeetCode Sample Questions

1101. The Earliest Moment When Everyone Become Friends

1. Sort by timestamp
2. Create array of size N, start with root as self
3. Perform union-find. End when size of a root group is N.

class Solution {
    int[] roots;      // Root of each node
    int[] sizes;      // Size of graph starting from this node
    public int earliestAcq(int[][] logs, int N) {
        roots = new int[N];
        sizes = new int[N];
            
        // Sort by timestamp ascending
        Arrays.sort(logs, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        
        // Initialize arrays. All graph start with itself and size 1
        Arrays.fill(sizes, 1);
        for (int i = 0; i < N; i++) {
            roots[i] = i;
        }
        
        // Perform union-find for each friendship
        for (int i = 0; i < logs.length; i++) {
            int[] log = logs[i];
            int time = log[0];
            int f1 = log[1];
            int f2 = log[2];
            
            int f1Root = findRoot(f1);
            int f2Root = findRoot(f2);
            
            if (f1Root == f2Root) {
                continue;
            }
            else {
                if (sizes[f1Root] < sizes[f2Root]) {
                    roots[f1Root] = f2Root;
                    sizes[f2Root] += sizes[f1Root];
                    if (sizes[f2Root] == N) return time;
                }
                else {
                    roots[f2Root] = f1Root;
                    sizes[f1Root] += sizes[f2Root];
                    if (sizes[f1Root] == N) return time;
                }
            }
        }
        
        return -1;
    }
    
    private int findRoot(int node) {
        // Find root
        int root = node;
        while (root != roots[root]) {
            root = roots[root];
        }
        
        // Do compression
        int parent = roots[node];
        while (parent != root) {
            roots[node] = root;
            node = parent;
            parent = roots[node];
        }
        
        return root;
    }
}