lthieu's notes

07-Union-Find

12 min read

Buổi 07 — Union-Find (Disjoint Set Union)

Navigation

← 06-String-Matching-Trie | → 08-Weighted-Graphs Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐

1. Analogy & Context

Union-Find = Nhóm bạn bè ở trường học

Hình dung buổi đầu nhập học: mỗi học sinh là một “nhóm” riêng lẻ. Khi hai người kết bạn, nhóm của họ hợp nhất. Sau một thời gian, hỏi “A và B có phải bạn bè không?” = “Họ có cùng nhóm không?”

Cách trả lời: tìm trưởng nhóm (root/representative) của cả A và B. Nếu cùng trưởng nhóm → cùng nhóm → là bạn bè.

Hai thao tác cốt lõi:

  • find(x) — Ai là trưởng nhóm của x?
  • union(x, y) — Gộp nhóm của x và y lại

Path Compression — Tối ưu hóa: Sau khi tìm trưởng nhóm, kết nối thẳng tất cả các thành viên trên đường đi trực tiếp vào trưởng nhóm. Lần sau hỏi cùng người → O(1) luôn.

Tại sao gọi là "Disjoint Set"?

Các nhóm không giao nhau — mỗi phần tử chỉ thuộc đúng một nhóm. Khi union hai nhóm, chúng hợp nhất hoàn toàn thành một, không có phần tử nào thuộc cả hai nhóm cũ nữa.

2. The FAANG Standard

Union-Find trong các vòng phỏng vấn FAANG

  • Facebook/Meta: Accounts merge, friend network, social graph connectivity
  • Amazon: Delivery zones, warehouse connectivity, network outage detection
  • Google: Map regions, network infrastructure, Kruskal’s MST cho network design
  • Microsoft: Active Directory groups, file system permissions

Union-Find vs BFS/DFS cho connectivity:

Tiêu chíUnion-FindBFS/DFS
Static graphO(α(N)) per queryO(V+E) one-time
Dynamic graph (edges added)O(α(N)) ← WinnerRebuild mỗi lần
Detect cycleO(α(N))O(V+E)
Find actual pathKhông thểCó thể
MemoryO(N)O(V+E)

Key insight

Union-Find tỏa sáng khi graph thay đổi liên tục (edges được thêm dần dần) và bạn cần query connectivity nhanh. BFS/DFS tốt hơn khi cần tìm đường đi thực tế.

Hàm Inverse Ackermann α(N): với mọi N thực tế (kể cả N = số nguyên tử trong vũ trụ). Nên coi như amortized.

3. Visual Thinking (Mermaid)

3.1 Union-Find Forest — Trước và Sau khi Union

graph TD
    subgraph Before ["Trước: 6 nhóm riêng lẻ"]
        A1((1))
        A2((2))
        A3((3))
        A4((4))
        A5((5))
        A6((6))
    end

    subgraph After ["Sau: union(1,2), union(3,4), union(2,3)"]
        R1((1 ROOT)) --> B2((2))
        R1 --> B3((3))
        R1 --> B4((4))
        A5b((5))
        A6b((6))
    end

    style R1 fill:#FF9800,color:#fff

3.2 Path Compression — Cây sâu vs Cây phẳng

graph TD
    subgraph Deep ["Trước Path Compression: cây sâu"]
        D1((1 root)) --> D2((2)) --> D3((3)) --> D4((4)) --> D5((5))
    end

    subgraph Flat ["Sau khi find(5): path compression"]
        F1((1 root)) --> F2((2))
        F1 --> F3((3))
        F1 --> F4((4))
        F1 --> F5((5))
    end

    style D1 fill:#FF9800,color:#fff
    style F1 fill:#4CAF50,color:#fff

Gọi find(5) trên cây sâu → tất cả nút trên đường đi đều trỏ thẳng vào root.

3.3 Union by Rank — Luôn gắn cây thấp hơn vào cây cao hơn

graph TD
    subgraph Wrong ["Sai: gắn cây cao vào cây thấp"]
        W_root((rank=0)) --- W1((rank=2)) --- W2((x)) --- W3((y)) --- W4((z))
    end

    subgraph Correct ["Đúng: cây rank thấp hơn gắn vào cây rank cao hơn"]
        C_root((rank=2 ROOT)) --> C1((x)) --> C2((y)) --> C3((z))
        C_root --> C_small((rank=0))
    end

    style C_root fill:#4CAF50,color:#fff

4. TypeScript Template

4.1 UnionFind Class — Complete with Path Compression + Union by Rank

class UnionFind {
  private parent: number[];
  private rank: number[];
  private componentCount: number;
 
  constructor(n: number) {
    // CRITICAL: parent[i] = i, NOT parent[i] = 0
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.componentCount = n;
  }
 
  // Path compression — iterative (preferred in interviews)
  find(x: number): number {
    while (this.parent[x] !== x) {
      // Path halving: point to grandparent (simpler than full compression)
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
 
  // Alternative: recursive path compression (full compression)
  findRecursive(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.findRecursive(this.parent[x]); // flatten to root
    }
    return this.parent[x];
  }
 
  // Union by rank — returns true if actually merged (was in different components)
  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);
 
    if (rootX === rootY) return false; // already same component
 
    // Attach smaller rank tree under larger rank tree
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      // Same rank: pick one as root, increment its rank
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
 
    this.componentCount--;
    return true;
  }
 
  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
 
  getComponentCount(): number {
    return this.componentCount;
  }
}

4.2 Number of Connected Components

// LeetCode #323 — Number of Connected Components in Undirected Graph
function countComponents(n: number, edges: number[][]): number {
  const uf = new UnionFind(n);
 
  for (const [u, v] of edges) {
    uf.union(u, v);
  }
 
  return uf.getComponentCount();
}

4.3 Redundant Connection — Tìm cạnh tạo chu trình

// LeetCode #684 — Redundant Connection
// Graph ban đầu là tree, thêm 1 edge tạo cycle. Tìm edge đó.
function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const uf = new UnionFind(n + 1); // nodes 1-indexed
 
  for (const [u, v] of edges) {
    // If u and v already connected → this edge creates a cycle
    if (!uf.union(u, v)) {
      return [u, v];
    }
  }
 
  return []; // shouldn't reach here per problem guarantee
}

4.4 Accounts Merge — Union-Find trên Strings với HashMap

// LeetCode #721 — Accounts Merge (Most Complex Union-Find Problem)
// Xem Section 8 cho full solution

4.5 Count Islands — Union-Find Variation

// LeetCode #200 — Number of Islands với Union-Find
function numIslands(grid: string[][]): number {
  const ROWS = grid.length;
  const COLS = grid[0].length;
 
  // Convert 2D to 1D index: (r, c) → r * COLS + c
  const n = ROWS * COLS;
  const uf = new UnionFind(n);
  let waterCount = 0; // Track water cells to subtract from total
 
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
 
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      if (grid[r][c] === '0') {
        waterCount++;
        continue;
      }
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS && grid[nr][nc] === '1') {
          uf.union(r * COLS + c, nr * COLS + nc);
        }
      }
    }
  }
 
  return uf.getComponentCount() - waterCount;
}

4.6 Number of Operations to Make Network Connected

// LeetCode #1319
// N computers, some connected by cables. Min cables needed to connect all?
function makeConnected(n: number, connections: number[][]): number {
  if (connections.length < n - 1) return -1; // impossible: need at least n-1 cables
 
  const uf = new UnionFind(n);
  let extraCables = 0;
 
  for (const [u, v] of connections) {
    if (!uf.union(u, v)) {
      extraCables++; // redundant cable = can be reused
    }
  }
 
  const componentsNeeded = uf.getComponentCount() - 1;
  return extraCables >= componentsNeeded ? componentsNeeded : -1;
}

5. Complexity Deep-dive

Phân tích độ phức tạp theo từng optimization

Không có optimization nào:

  • find: — có thể thành linked list
  • N operations:

Chỉ có Path Compression:

  • find: amortized
  • N operations:

Chỉ có Union by Rank:

  • find: worst case
  • N operations:

Cả hai (Path Compression + Union by Rank):

  • find: amortized ≈
  • N operations:
  • = Inverse Ackermann function — tăng cực kỳ chậm

Bảng so sánh thực tế:

N
10≤ 4
20≤ 4
(atoms in universe)266≤ 5

Space complexity

— hai arrays parent và rank, mỗi array N phần tử.

6. Edge Cases & Pitfalls

Những lỗi phổ biến gây failed test case

Lỗi #1: Khởi tạo parent sai

// BUG: parent[i] = 0 cho tất cả
this.parent = new Array(n).fill(0);
// → find(0) = 0 (đúng), find(1) = 0 (SAI! 1's parent should be itself)
 
// FIX:
this.parent = Array.from({ length: n }, (_, i) => i);

Lỗi #2: find() không đệ quy đến root

// BUG: Chỉ lấy parent một lần
find(x: number): number {
  return this.parent[x]; // WRONG: có thể trả về intermediate node, không phải root
}
 
// FIX: Phải loop/recurse cho đến khi parent[x] === x
find(x: number): number {
  while (this.parent[x] !== x) x = this.parent[x];
  return x;
}

Lỗi #3: Union không dùng root

// BUG: Union trực tiếp x và y thay vì roots
union(x: number, y: number): void {
  this.parent[x] = y; // WRONG! x và y có thể không phải root
}
 
// FIX:
union(x: number, y: number): void {
  const rootX = this.find(x); // Phải tìm root trước
  const rootY = this.find(y);
  if (rootX !== rootY) this.parent[rootX] = rootY;
}

Lỗi #4: Quên check “đã connected” trước khi union

// Nhiều bài yêu cầu detect khi edge là redundant
// Phải check connected() TRƯỚC union()
if (uf.connected(u, v)) {
  return [u, v]; // This edge creates a cycle
}
uf.union(u, v);

Lỗi #5: 1-indexed nodes

// Nhiều bài LeetCode dùng nodes từ 1 đến N
// BUG: Khởi tạo UnionFind(n) → nodes 0 to n-1 (index out of range cho node n)
// FIX: UnionFind(n + 1) để có room cho node n
const uf = new UnionFind(n + 1);

accountsMerge — Pitfall đặc biệt

Bài #721 dùng email strings làm key, nhưng find() cần integer index. Cần mapping email → id bằng HashMap. Canonical name của merged account = tên của account sở hữu email đầu tiên gặp — phải track riêng.

7. Pattern Recognition

Nhận diện bài Union-Find trong 30 giây

Keywords gợi ý Union-Find:

  • “connected components” / “số lượng nhóm”
  • “dynamic connectivity” — edges được thêm dần dần
  • “redundant connection” / “detect cycle in undirected graph”
  • “are X and Y in the same group/region?”
  • “friends / provinces / cliques / clusters”
  • “merge accounts/emails/users”
  • “Kruskal’s Minimum Spanning Tree”
  • “number of islands II” — islands được thêm dần (dynamic)

Phân biệt Union-Find với BFS/DFS:

Graph cho sẵn, hỏi static connectivity   → BFS/DFS
Edges được thêm dần, hỏi connectivity    → Union-Find
Cần tìm đường đi thực tế                  → BFS/DFS
Chỉ cần biết "có connected không?"        → Union-Find (nhanh hơn)
Cycle detection trong undirected graph    → Union-Find (đơn giản hơn)
Cycle detection trong directed graph      → DFS với visited states

Union-Find cho Kruskal's MST

Kruskal = Sort edges by weight → greedily add cheapest edge that doesn’t create cycle. “Doesn’t create cycle” = !uf.connected(u, v). Thêm edge = uf.union(u, v). Stop khi n-1 edges added.

8. Top LeetCode Problems

#Tên bàiĐộ khóKey technique
#547Number of ProvincesMediumBasic Union-Find
#684Redundant ConnectionMediumCycle detection
#721Accounts MergeMediumUnion-Find + HashMap
#1319Make Network ConnectedMediumExtra edges counting
#305Number of Islands IIHardDynamic Union-Find
#952Largest Component by FactorHardMath + Union-Find
#1202Smallest String With SwapsMediumUnion-Find + grouping
#323Connected ComponentsMediumDirect application

Complete Solution: #721 Accounts Merge (Hard Union-Find Application)

Bài #721 là bài Union-Find khó nhất thường gặp. Yêu cầu kết hợp Union-Find + HashMap + sorting.

Problem: Mỗi account = [name, email1, email2, …]. Nếu hai accounts có chung email → cùng người. Merge lại, sort emails.

// LeetCode #721 — Accounts Merge
// Time: O(N*L*α(N)) where N = total emails, L = max account length
// Space: O(N) for Union-Find + HashMap
 
function accountsMerge(accounts: string[][]): string[][] {
  // Step 1: Map each email to a unique integer ID
  const emailToId = new Map<string, number>();
  const emailToName = new Map<string, string>();
  let id = 0;
 
  for (const account of accounts) {
    const name = account[0];
    for (let i = 1; i < account.length; i++) {
      const email = account[i];
      if (!emailToId.has(email)) {
        emailToId.set(email, id++);
        emailToName.set(email, name); // store owner name (first occurrence)
      }
    }
  }
 
  // Step 2: Union all emails in the same account
  const uf = new UnionFind(id);
  for (const account of accounts) {
    // Union all emails in this account with the first email
    const firstEmailId = emailToId.get(account[1])!;
    for (let i = 2; i < account.length; i++) {
      uf.union(firstEmailId, emailToId.get(account[i])!);
    }
  }
 
  // Step 3: Group emails by their root representative
  const rootToEmails = new Map<number, string[]>();
  for (const [email, emailId] of emailToId.entries()) {
    const root = uf.find(emailId);
    if (!rootToEmails.has(root)) rootToEmails.set(root, []);
    rootToEmails.get(root)!.push(email);
  }
 
  // Step 4: Build result — sort emails, prepend name
  const result: string[][] = [];
  for (const [root, emails] of rootToEmails.entries()) {
    emails.sort(); // lexicographical sort
    // Find owner name: look up any email in this group
    const name = emailToName.get(emails[0])!;
    result.push([name, ...emails]);
  }
 
  return result;
}
 
// Test
console.log(accountsMerge([
  ["John","johnsmith@mail.com","john_newyork@mail.com"],
  ["John","johnsmith@mail.com","john00@mail.com"],
  ["Mary","mary@mail.com"],
  ["John","johnnybravo@mail.com"]
]));
/*
Expected:
[
  ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
  ["Mary","mary@mail.com"],
  ["John","johnnybravo@mail.com"]
]
*/

Giải thích từng bước

  1. emailToId: mỗi email duy nhất nhận một integer ID (cần để dùng UnionFind array)
  2. Union step: trong mỗi account, union tất cả emails lại với nhau (dùng email[1] làm anchor)
  3. Group by root: sau path compression, find(emailId) trả về cùng root cho tất cả emails của cùng người
  4. Sort + prepend name: sort emails trong mỗi group, thêm tên vào đầu

9. Self-Assessment Checklist

Kiểm tra bản thân trước khi interview

  • Implement UnionFind từ đầu trong < 5 phút (với path compression + union by rank)
  • Giải thích tại sao parent[i] = i (không phải 0) khi khởi tạo
  • Nói được tại sao find() phải loop đến khi parent[x] === x
  • Implement path compression (iterative) và giải thích tác dụng
  • Giải thích union by rank: tại sao gắn cây rank thấp vào cây rank cao
  • Phân biệt khi nào dùng Union-Find vs BFS/DFS cho connectivity
  • Giải bài redundantConnection (detect cycle) bằng Union-Find
  • Giải bài accountsMerge: mapping email → id, union, group by root
  • Biết là gì và tại sao coi như O(1)
  • Handle 1-indexed nodes: UnionFind(n+1) thay vì UnionFind(n)

Quick revision — 15 phút

Tập trung vào: UnionFind class (find với path halving + union by rank), redundantConnection (check before union), và accountsMerge (email→id mapping).

Graph View

Backlinks