Number of Connected Components 解題教學:3 種解法完整比較|LeetCode 323 Best Practice

Number of Connected Components 解題教學示意圖|LeetCode 323

本文完整拆解 LeetCode 323 Number of Connected Components 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Number of Connected Components 一次弄懂。

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link


You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no repeated edges.

Python

				
					# time complexity: O(V + E * α(n)) is the inverse Ackermann function
# space complexity: O(V)
from typing import List


class UnionFind():
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, node):
        while node != self.parents[node]:
            node = self.parents[node]
        return node

    def uion(self, nodeX, nodeY):
        parentX = self.find(nodeX)
        parentY = self.find(nodeY)

        if parentX == parentY:
            return

        if self.rank[parentX] > self.rank[parentY]:
            self.parents[parentY] = self.parents[parentX]
        elif self.rank[parentX] < self.rank[parentY]:
            self.parents[parentX] = self.parents[parentY]
        else:
            self.parents[parentX] = self.parents[parentY]
            self.rank[parentY] += 1


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        disjointUnionSet = UnionFind(n)
        for startVertex, endVertex in edges:
            disjointUnionSet.uion(startVertex, endVertex)

        parent = set()
        for i in range(n):
            parent.add(disjointUnionSet.find(i))
        return len(set(parent))


n = 4
edges = [[0, 1], [2, 3], [1, 2]]
print(Solution().countComponents(n, edges))
				
			

Number of Connected Components in an Undirected Graph 解題思路

計算無向圖的連通分量,最直接的想法是:從每個還沒走訪過的節點出發做一次 DFS,能走到的都屬於同一塊,走完就代表找到一個分量。另一個等價解法是並查集——一開始每個節點自成一塊,每合併一條邊成功就把分量數減一。

Number of Connected Components in an Undirected Graph 演算法步驟

  1. 用鄰接表建圖,建立長度 n 的 visited 陣列。
  2. 走訪 0 到 n-1 的每個節點。
  3. 若尚未走訪,計數器加一,並從該節點做一次 DFS 把整塊標記為已訪。
  4. 所有節點處理完後回傳計數器。

Number of Connected Components in an Undirected Graph 複雜度分析

項目複雜度
時間複雜度O(V+E)
空間複雜度O(V+E)

建圖需要走訪所有邊,DFS 總共走訪每個節點與每條邊各一次,時間為 O(V+E)。鄰接表佔 O(V+E),visited 與遞迴堆疊佔 O(V)。並查集版本時間接近 O(E α(V))。

Number of Connected Components in an Undirected Graph 的邊界情況與常見錯誤

  • 孤立節點(沒有任何邊)本身就是一個分量,不能漏算。
  • 無向邊要在鄰接表的兩端都加入。
  • 邊的清單可能為空,此時答案等於節點數 n。
  • 並查集版本記得做路徑壓縮,否則會退化。

Number of Connected Components in an Undirected Graph 其他解法比較

解法時間空間說明
對每個節點跑一次 BFSO(V+E)O(V+E)與 DFS 等價
並查集O(E α(V))O(V)適合邊會動態加入的情境
鄰接表 + DFSO(V+E)O(V+E)本文採用