Đếm số thành phần liên thông (Number of Connected Components) bằng Union-Find — path compression và union by rank để làm gì?

Ý tưởng: Khởi tạo mỗi đỉnh là một thành phần riêng (count = n). Mỗi cạnh, union hai đầu; nếu chúng chưa cùng nhóm thì giảm count. Kết quả là số nhóm còn lại.

Hai tối ưu:
- Path compression: trong find, trỏ thẳng node về gốc → các lần sau gần như O(1).
- Union by rank/size: luôn gắn cây thấp vào cây cao → tránh cây bị thoái hóa thành chuỗi.

Kết hợp cả hai cho độ phức tạp gần như hằng số (α — hàm Ackermann ngược).

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i)
  const rank = new Array(n).fill(1)
  const find = (x: number): number => {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x] } // nén đường
    return x
  }
  let count = n
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b)
    if (ra === rb) continue
    if (rank[ra] < rank[rb]) parent[ra] = rb
    else if (rank[ra] > rank[rb]) parent[rb] = ra
    else { parent[rb] = ra; rank[ra]++ }
    count--
  }
  return count
}

Độ phức tạp: ~O(V + E·α(V)) thời gian, O(V) bộ nhớ.

Lưu ý: Cũng giải được bằng DFS/BFS O(V+E); Union-Find vượt trội khi cạnh đến động (streaming) hoặc cần hỏi liên thông nhiều lần.

Idea: Start each vertex as its own component (count = n). For each edge, union the endpoints; if they weren't already in the same group, decrement count. The result is the remaining group count.

Two optimizations:
- Path compression: in find, point nodes straight to the root → near-O(1) afterwards.
- Union by rank/size: always attach the shorter tree under the taller → avoids degenerating into a chain.

Together they give near-constant complexity (α — inverse Ackermann).

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i)
  const rank = new Array(n).fill(1)
  const find = (x: number): number => {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x] } // path compression
    return x
  }
  let count = n
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b)
    if (ra === rb) continue
    if (rank[ra] < rank[rb]) parent[ra] = rb
    else if (rank[ra] > rank[rb]) parent[rb] = ra
    else { parent[rb] = ra; rank[ra]++ }
    count--
  }
  return count
}

Complexity: ~O(V + E·α(V)) time, O(V) space.

Note: DFS/BFS also solve it in O(V+E); Union-Find wins when edges arrive dynamically (streaming) or you query connectivity many times.