20. Union-Find (Disjoint Set)

🧸 ELI5: Imagine everyone at a party starts in their own tiny friend group of 1. Whenever two people become friends, you merge their whole friend groups into one. Union-Find quickly answers: "are Alice and Bob in the same friend group?" and "merge these two groups together" — both almost instantly, even with millions of people.

🌍 Real life: Detecting if adding a road would create a cycle (used in building efficient road networks — Kruskal's algorithm). Grouping friends into "friend circles" on a social network. Detecting connected components in an image (like the "magic wand" tool in Photoshop grouping similar-colored pixels).

📝 Pseudocode:

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   // path compression: flatten the group
    return parent[x]

function union(x, y):
    rootX = find(x)
    rootY = find(y)
    if rootX != rootY:
        parent[rootX] = rootY          // merge the two groups

🐹 Go:

package main

import "fmt"

type UnionFind struct {
	parent []int
}

func NewUnionFind(n int) *UnionFind {
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i // everyone starts as their own group leader
	}
	return &UnionFind{parent: parent}
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x]) // flatten the chain on the way up
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
	rootX, rootY := uf.Find(x), uf.Find(y)
	if rootX != rootY {
		uf.parent[rootX] = rootY // merge the friend groups
	}
}

func main() {
	people := NewUnionFind(5) // people 0,1,2,3,4
	people.Union(0, 1)        // 0 and 1 become friends
	people.Union(1, 2)        // now 0,1,2 are one group

	fmt.Println(people.Find(0) == people.Find(2)) // true, same group
	fmt.Println(people.Find(0) == people.Find(3)) // false, different group
}

🇨 C — the "path compression" line (uf->parent[x] = uf_find(uf, uf->parent[x])) is the entire trick: every lookup flattens the chain a little more, so future lookups get faster:

#include <stdio.h>

typedef struct { int parent[64]; } UnionFind;

void uf_init(UnionFind *uf, int n) {
    for (int i = 0; i < n; i++) uf->parent[i] = i; // everyone starts as their own group leader
}

int uf_find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) uf->parent[x] = uf_find(uf, uf->parent[x]); // flatten on the way up
    return uf->parent[x];
}

void uf_union(UnionFind *uf, int x, int y) {
    int root_x = uf_find(uf, x), root_y = uf_find(uf, y);
    if (root_x != root_y) uf->parent[root_x] = root_y; // merge the friend groups
}

int main(void) {
    UnionFind people;
    uf_init(&people, 5); // people 0,1,2,3,4
    uf_union(&people, 0, 1); // 0 and 1 become friends
    uf_union(&people, 1, 2); // now 0,1,2 are one group

    printf("%d\n", uf_find(&people, 0) == uf_find(&people, 2)); // 1 (true), same group
    printf("%d\n", uf_find(&people, 0) == uf_find(&people, 3)); // 0 (false), different group
    return 0;
}

⏱️ Complexity: With path compression, find/union are nearly O(1) (technically O(α(n)), an incredibly slow-growing function — for all practical purposes, instant).