323. Number of Connected Components in an Undirected Graph

Medium

Description

給定 n 個節點（編號 0 到 n-1）和一組無向邊 edges，回傳圖中連通分量的數量。

Example:

Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2

Intuition#

計算無向圖的連通分量數 – 用 DFS/BFS 遍歷或 Union-Find 合併。

連通分量 = 彼此可達的節點群
DFS/BFS：從每個未訪問節點啟動遍歷，每次啟動代表一個新的連通分量
Union-Find：合併所有邊，最後計算不同的根節點數

Approaches#

1: DFS#

概念: 建鄰接表，從每個未訪問節點啟動 DFS，計數啟動次數
時間複雜度: O(V + E)
空間複雜度: O(V + E)

class Solution {
    fun countComponents(n: Int, edges: Array<IntArray>): Int {
        val graph = Array(n) { mutableListOf<Int>() }
        for ((u, v) in edges) {
            graph[u].add(v)
            graph[v].add(u)
        }

        val visited = BooleanArray(n)
        var count = 0

        fun dfs(node: Int) {
            visited[node] = true
            for (next in graph[node]) {
                if (!visited[next]) dfs(next)
            }
        }

        for (i in 0 until n) {
            if (!visited[i]) {
                count++
                dfs(i)
            }
        }
        return count
    }
}

⭐2: Union-Find#

概念: 初始每個節點為獨立集合（共 n 個），每次成功 union 連通分量數減一
時間複雜度: O(E * α(n))
空間複雜度: O(n)

class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray

    fun countComponents(n: Int, edges: Array<IntArray>): Int {
        parent = IntArray(n) { it }
        rank = IntArray(n)
        var components = n

        for ((u, v) in edges) {
            if (union(u, v)) components--
        }
        return components
    }

    private fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    private fun union(x: Int, y: Int): Boolean {
        val px = find(x)
        val py = find(y)
        if (px == py) return false
        if (rank[px] < rank[py]) parent[px] = py
        else if (rank[px] > rank[py]) parent[py] = px
        else { parent[py] = px; rank[px]++ }
        return true
    }
}

🔑 Takeaways#

Pattern: 連通分量計數 – DFS 計數啟動次數 / Union-Find 計數合併次數
關鍵技巧: Union-Find 的 components = n - 成功 union 次數；此題是 Union-Find 的最基本應用