Pattern · Tìm kiếm theo chiều sâuTrung bình ~25 phút đọc + làm

Đếm Thành Phần Liên ThôngNumber of Connected Components

Hiểu bài

Cho đồ thị vô hướng với n nút (đánh số 0 đến n-1) và danh sách cạnh edges. Đếm số thành phần liên thông trong đồ thị.

Ví dụ:

n = 5, edges = [[0,1],[1,2],[3,4]]
output = 2
// Thành phần 1: {0,1,2} — liên thông nhau
// Thành phần 2: {3,4}   — liên thông nhau
// Nút cô lập cũng là 1 thành phần riêng

n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
output = 1  // toàn bộ đồ thị liên thông

Mỗi lần DFS từ nút chưa thăm sẽ "ăn" hết 1 thành phần liên thông — đếm số lần gọi DFS = số thành phần.

Cách cơ bảnO(E × α(n)) time ≈ O(E) — α là hàm Ackermann ngược, gần như O(1)

// Union-Find đơn giản — trực quan cho bài này
function countComponentsUF(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i)

  function find(x: number): number {
    if (parent[x] !== x) parent[x] = find(parent[x])
    return parent[x]
  }

  function union(x: number, y: number): boolean {
    const px = find(x), py = find(y)
    if (px === py) return false
    parent[px] = py
    return true
  }

  let components = n
  for (const [a, b] of edges) {
    if (union(a, b)) components--
  }
  return components
}

Vì sao cách này chậm:

Union-Find rất hiệu quả cho bài này nhưng cần nhớ thêm pattern.

DFS với mảng visited đơn giản hơn trong phỏng vấn và cũng đạt O(V+E).

Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan

Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.

Mở khoá Pro Xem Lifetime

Hiểu bài

Cho đồ thị vô hướng với n nút (đánh số 0 đến n-1) và danh sách cạnh edges. Đếm số thành phần liên thông trong đồ thị.

Ví dụ:

n = 5, edges = [[0,1],[1,2],[3,4]]
output = 2
// Thành phần 1: {0,1,2} — liên thông nhau
// Thành phần 2: {3,4}   — liên thông nhau
// Nút cô lập cũng là 1 thành phần riêng

n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
output = 1  // toàn bộ đồ thị liên thông

Mỗi lần DFS từ nút chưa thăm sẽ "ăn" hết 1 thành phần liên thông — đếm số lần gọi DFS = số thành phần.

// Union-Find đơn giản — trực quan cho bài này function countComponentsUF(n: number, edges: number[][]): number { const parent = Array.from({ length: n }, (_, i) => i) function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]) return parent[x] } function union(x: number, y: number): boolean { const px = find(x), py = find(y) if (px === py) return false parent[px] = py return true } let components = n for (const [a, b] of edges) { if (union(a, b)) components-- } return components }