題目
#

leetcode 323 - Number of Connected Components in an Undirected Graph (題目說明請點連結)

題目簡述
#

給定一個無向圖的節點數 n 和邊的列表 edges，請計算圖中Connected Components的數量。
Connected Components是指圖中任意兩個節點之間都存在路徑的最大連通子圖。

範例
#

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: 圖中有 5 個節點，邊為 [0,1], [1,2], [3,4]。
連通分量 1: 0-1-2
連通分量 2: 3-4
總共有 2 個連通分量。

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Explanation: 圖中有 5 個節點，邊為 [0,1], [1,2], [2,3], [3,4]。
所有節點都連通：0-1-2-3-4
總共有 1 個連通分量。

Example 3:

Input: n = 3, edges = []
Output: 3
Explanation: 圖中有 3 個節點，沒有邊。
每個節點都是獨立的連通分量：0, 1, 2
總共有 3 個連通分量。

解題思路
#

這題要求我們計算無向圖中Connected Components的數量。我們可以使用深度優先搜尋（DFS）來解決這個問題，具體方法是遍歷圖中的每個節點，對於每個未訪問的節點，使用 DFS 遍歷其所在的 Connected Components，並計數 Connected Components 的數量。

解法
#

深度優先搜尋法（Depth-First Search Approach）

使用 adjacency list 構建無向圖
創建 visited 陣列來記錄已訪問的節點
遍歷所有節點，對於每個未訪問的節點：
- 使用 DFS 遍歷其所在的Connected Components
- 將count加 1
返回Connected Components的總數量

步驟
#

構建圖：
- 創建 adjacency list 表示無向圖
- 對於每條邊 [u, v]，在兩個方向都添加連接
DFS 遍歷：
- 遍歷所有節點，對於每個未訪問的節點
- 使用 DFS 遍歷其所在的Connected Components
- 標記所有訪問過的節點
計數 Connected Components：
- 每次開始新的 DFS 時，count加 1
返回結果：
- 返回Connected Components的總數量

例子說明
#

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

graph TD; A[0] B[1] C[2] D[3] E[4] A --- B B --- C D --- E

步驟	當前節點	是否已訪問	操作	count	已訪問節點
初始化	-	-	創建圖和 `visited` 陣列	0	[]
第 1 步	0	否	`DFS(0)`，遍歷 `0-1-2`	1	[0,1,2]
第 2 步	1	是	跳過（已訪問）	1	[0,1,2]
第 3 步	2	是	跳過（已訪問）	1	[0,1,2]
第 4 步	3	否	`DFS(3)`，遍歷 `3-4`	2	[0,1,2,3,4]
第 5 步	4	是	跳過（已訪問）	2	[0,1,2,3,4]

最終結果： 2

DFS 遍歷過程說明：

DFS(0)：遍歷Connected Components {0, 1, 2}，count變為 1
DFS(3)：遍歷Connected Components {3, 4}，count變為 2
節點 1, 2, 4：都已訪問，跳過

Connected Components：

Connected Components 1：0-1-2
Connected Components 2：3-4

完整程式碼
#

java

import java.util.*;

class Solution {
    public int countComponents(int n, int[][] edges) {
        // 構建 adjacency list 表示的無向圖
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 添加邊：對於無向圖，需要在兩個方向都添加連接
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        // 創建 visited 陣列來記錄已訪問的節點
        boolean[] visited = new boolean[n];
        int count = 0; // Connected Components 計數器

        // 遍歷所有節點
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 對未訪問的節點進行 DFS，遍歷其所在的 Connected Components
                dfs(graph, visited, i);
                count++; // 每開始一次新的 DFS，count 加 1
            }
        }

        // 返回 Connected Components 的總數量
        return count;
    }

    // DFS 方法：遍歷從 node 開始的 Connected Components
    private void dfs(List<List<Integer>> graph, boolean[] visited, int node) {
        visited[node] = true; // 標記當前節點為已訪問
        
        // 遞迴訪問所有相鄰的未訪問節點
        for (int nei : graph.get(node)) {
            if (!visited[nei]) {
                dfs(graph, visited, nei);
            }
        }
    }
}

時間複雜度
#

時間複雜度：O(V + E)，其中 V 是節點數量，E 是邊的數量
- 構建圖：O(V + E)
- DFS 遍歷：每個節點和邊最多訪問一次，O(V + E)
- 總時間複雜度為 O(V + E)
空間複雜度：O(V + E)
- 圖的儲存：O(V + E)
- visited 陣列：O(V)
- DFS 遞迴調用棧：最壞情況下 O(V)
- 總空間複雜度為 O(V + E)