Tracking Connected Components

[!NOTE] This module explores the core principles of Union-Find (Disjoint Set Union), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: Given a set of elements, we want to:

1. Union(A, B): Connect element A and element B.
2. Find(A): Determine which group (component) A belongs to.

Applications: Kruskal’s MST Algorithm, Cycle Detection in Undirected Graphs, Grid Connectivity (Number of Islands).

Optimization:

• Path Compression: Point nodes directly to the root during find.
• Union by Rank/Size: Attach the smaller tree to the larger tree to keep height low.
• Result: Time complexity becomes O(alpha(N)) (Inverse Ackermann function), which is effectively O(1) for all practical N.

---

2. Interactive Analysis

Union nodes and watch them merge. Find highlights the path to the representative (Root).

Parents: [0, 1, 2, 3, 4, 5]

---

3. Implementation

Java

Go

class DSU {
    int[] parent;
    int[] rank;

    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]); // Path Compression
        }
        return parent[i];
    }

    public boolean union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by Rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            return true;
        }
        return false;
    }
}

type DSU struct {
    parent []int
    rank   []int
}

func NewDSU(n int) *DSU {
    p := make([]int, n)
    for i := range p { p[i] = i }
    return &DSU{parent: p, rank: make([]int, n)}
}

func (d *DSU) Find(i int) int {
    if d.parent[i] != i {
        d.parent[i] = d.Find(d.parent[i]) // Path Compression
    }
    return d.parent[i]
}

func (d *DSU) Union(i, j int) bool {
    rootI := d.Find(i)
    rootJ := d.Find(j)
    if rootI != rootJ {
        // Union by Rank
        if d.rank[rootI] > d.rank[rootJ] {
            d.parent[rootJ] = rootI
        } else if d.rank[rootI] < d.rank[rootJ] {
            d.parent[rootI] = rootJ
        } else {
            d.parent[rootJ] = rootI
            d.rank[rootI]++
        }
        return true
    }
    return false
}

---

4. Complexity Analysis

Operation	Time	Space	Notes
Union	O(α(N))	O(N)	Nearly constant time.
Find	O(α(N))	O(N)	Amortized.

α(N) is the Inverse Ackermann function. For all practical values of N (even universe size), α(N) ≤ 4.