Coding - Union Find

Imagine you’re organizing a large function where members of different families gather. Your task is to assign table numbers to families while ensuring:

1. Each family gets a unique table number.
2. You can quickly determine if two people belong to the same family.
3. You can efficiently merge tables if two families need to sit together.

Similarly, consider a network of computers. Each computer can communicate with others if they are connected directly or indirectly. How many cables will you need to connect all computers or check if adding one creates a cycle? You solve these problems by Union-Find algorithm.

It is a powerful tool for solving problems involving:

• Connected Components: Counting isolated groups in a network.
• Dynamic Connectivity: Determining if two nodes are connected dynamically.
• Cycle Detection: Checking if adding an edge creates a cycle in a graph.

"Families and Leaders"

Think of Union-Find as Managing Families:

1. Each family has a leader (or root) who represents the entire family.
2. Every family member knows who their leader is, directly or indirectly.
   1. Find Operation: If you ask a family member who their leader is, they will:
      1. Point to the leader directly.
      2. If unsure, point to someone else in the family who knows the leader. You keep following the chain until you find the leader.
3. Union Operation: When two families want to merge:
   1. Find the leaders of both families.
   2. Make one leader subordinate to the other, effectively merging the families under one leader.

Optimizations - How to Run Union and Find Faster?

1. Path Compression:

   • When someone finds their leader, they remember it for future queries. This reduces the time needed for subsequent operations and ensures all members directly point to the leader.

2. Rank Optimization:

   • When merging families, always attach the smaller family under the larger family. This way, the structure will be balanced. It minimizes the chain length, preventing any single path from growing disproportionately long.

Code Walkthrough

Imagine you have 6 people, each initially in their own family. Using the union operation, you start connecting people into larger families:

• Step 1: Person 0 and Person 1 become a family.
• Step 2: Person 2 and Person 3 form their own family.
• Step 3: The families of (0, 1) and (2, 3) merge into one big family.

Finding Family Leaders: When asked, "Who is the head of Person 3’s family?" the find operation quickly identifies Person 0 as the overall leader, avoiding unnecessary checks of the hierarchy.

Counting Total Families: By the end, you use the countComponents operation to determine there are 3 unique families left:

• Family 1: (0, 1, 2, 3)
• Family 2: (4)
• Family 3: (5)

// Create a UnionFind instance for 6 nodes (0 to 5)
const uf = new UnionFind(6);

// Initial state of the data structure
// parent = [0, 1, 2, 3, 4, 5] (each node is its own leader)
// rank   = [0, 0, 0, 0, 0, 0] (all nodes have rank 0)

// Start connecting family members
// Step 1: Union(0, 1) - Connect node 0 and 1
uf.union(0, 1);
// parent = [0, 0, 2, 3, 4, 5] (1's leader is now 0)
// rank   = [1, 0, 0, 0, 0, 0] (0's rank increased to 1)

// Step 2: Union(2, 3) - Connect node 2 and 3
uf.union(2, 3);
// parent = [0, 0, 2, 2, 4, 5] (3's leader is now 2)
// rank   = [1, 0, 1, 0, 0, 0] (2's rank increased to 1)

// Step 3: Union(1, 2) - Connect the groups of node 1 and node 2
uf.union(1, 2);
// parent = [0, 0, 0, 2, 4, 5] (2's leader is now 0, path compression applied)
// rank   = [2, 0, 1, 0, 0, 0] (0's rank increased to 2)

// Step 4: Find(3) - Find the leader of node 3
const leader3 = uf.find(3);
// parent = [0, 0, 0, 0, 4, 5] (path compression: 3 points directly to leader 0)
// leader3 = 0

// Step 5: Count components - Count the unique groups
const numComponents = uf.countComponents();
// unique leaders = [0, 4, 5]
// numComponents = 3

So there are 3 unique families left.

Data Structure Implementation

class UnionFind {
    constructor(size) {
        // Step 1: Initialize the parent and rank arrays
        this.parent = Array.from({ length: size }, (_, i) => i); // Each person is their own leader initially
        this.rank = Array(size).fill(0); // All ranks start at 0
    }

    // Step 2: Find the leader (root) of a node
    find(node) {
        if (this.parent[node] !== node) {
            // Path compression: Make every node on the path point directly to the leader
            this.parent[node] = this.find(this.parent[node]);
        }
        return this.parent[node];
    }

    // Step 3: Union two nodes (merge their groups)
    union(node1, node2) {
        const root1 = this.find(node1); // Find leader of node1
        const root2 = this.find(node2); // Find leader of node2

        if (root1 !== root2) {
            // Union by rank: Attach the smaller tree under the larger tree
            if (this.rank[root1] > this.rank[root2]) {
                this.parent[root2] = root1; // root1 becomes the leader
            } else if (this.rank[root1] < this.rank[root2]) {
                this.parent[root1] = root2; // root2 becomes the leader
            } else {
                // If ranks are equal, pick one as leader and increase its rank
                this.parent[root2] = root1;
                this.rank[root1]++;
            }
        }
    }

    // Step 4: Count the number of unique groups
    countComponents() {
        const uniqueLeaders = new Set();
        for (let i = 0; i < this.parent.length; i++) {
            uniqueLeaders.add(this.find(i)); // Find the leader of each node
        }
        return uniqueLeaders.size;
    }
}

When to Update Rank During Union?

Rank represents an upper bound on the height of a tree. It is a heuristic used to minimize the height of the trees, which directly improves the efficiency of the find operation. The rank is incremented only under specific conditions to ensure the optimization remains effective.

Key Rule: The rank is updated only when two groups (trees) of equal rank are merged. In this case:

• The height of the resulting tree increases by one.
• The rank of the new leader is incremented to reflect this change.

Rank is NOT Updated If One Tree's Rank is Greater:

• The smaller tree is attached under the larger tree.
• Since the larger tree’s height does not change, the rank remains the same.

Examples: Connecting a Network

You are given n computers and a list of connections where connections[i] = [a, b] represents a cable between computer a and computer b.
Determine the minimum number of operations to connect all computers, or return -1 if it’s not possible.

1. Check Feasibility: If connections.length < n - 1, return -1 (not enough cables).
2. Union-Find to Connect Computers: Use the union operation to group computers.
3. Count Connected Components: Use the countComponents method to determine the number of groups.
4. Calculate Minimum Operations: If there are x groups, you need x - 1 extra cables.
   1. If you have 2 groups, you need 1 cable to connect them.
   2. If you have 3 groups, you need 2 cables to connect them.
   3. In general, to connect x groups, you need x - 1 cables.

function makeConnected(n, connections) {
    if (connections.length < n - 1) return -1; // Not enough cables

    const uf = new UnionFind(n);
    for (const [a, b] of connections) {
        uf.union(a, b);
    }

    const x = uf.countComponents();
    return x - 1; // Extra cables needed
}

// Example Usage
const n = 6;
const connections = [
    [0, 1], [0, 2], [0, 3], [1, 4], [3, 5]
];
console.log(makeConnected(n, connections)); // Output: 1