Number of Provinces

題目描述

給定 n×n 的鄰接矩陣 isConnected，其中 isConnected[i][j] = 1 表示城市 i 和 j 直接相連。回傳省份（連通分量）的數量。

輸入: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出: 2
解釋: {0,1} 和 {2} 是兩個省份

輸入: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出: 3
解釋: 三個城市各自獨立

解題思路

遍歷每個城市

依序檢查 0 到 n-1

未訪問則 DFS

從該城市出發 DFS，標記所有可達城市

計數 +1

每次啟動新的 DFS 代表發現一個新省份

跳過已訪問

已訪問的城市直接跳過

程式碼

C#

csharp

public class Solution {
    // DFS 解法
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        var visited = new bool[n];
        int provinces = 0;
 
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Dfs(isConnected, visited, i);
                provinces++; // 發現新省份
            }
        }
        return provinces;
    }
 
    private void Dfs(int[][] grid, bool[] visited, int city) {
        visited[city] = true;
        for (int j = 0; j < grid.Length; j++) {
            if (grid[city][j] == 1 && !visited[j]) {
                Dfs(grid, visited, j);
            }
        }
    }
}

TypeScript

typescript

function findCircleNum(isConnected: number[][]): number {
    const n = isConnected.length;
    const visited = new Array(n).fill(false);
    let provinces = 0;
 
    function dfs(city: number): void {
        visited[city] = true;
        for (let j = 0; j < n; j++) {
            if (isConnected[city][j] === 1 && !visited[j]) {
                dfs(j);
            }
        }
    }
 
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            provinces++;
        }
    }
    return provinces;
}

Python

python

def findCircleNum(isConnected: list[list[int]]) -> int:
    n = len(isConnected)
    visited = [False] * n
    provinces = 0
 
    def dfs(city):
        visited[city] = True
        for j in range(n):
            if isConnected[city][j] == 1 and not visited[j]:
                dfs(j)
 
    for i in range(n):
        if not visited[i]:
            dfs(i)
            provinces += 1
    return provinces

複雜度分析

| | Time | Space | |--|------|-------| | DFS | O(n²) | O(n) | | Union-Find | O(n² × α(n)) | O(n) |

n 是城市數。α 是反 Ackermann 函數，幾乎是常數。

圖解

City 0

相連→

City 1

→

City 2

進階觀點

💡面試追問

Union-Find 解法：初始化 n 個獨立集合，遍歷矩陣上三角，遇到 isConnected[i][j] == 1 就 union(i, j)。最終不同的根數量就是省份數。面試中展示兩種方法加分。

鄰接矩陣 vs 鄰接表：這題給的是鄰接矩陣，所以 DFS 每個城市要掃描整行 O(n)。如果是鄰接表，DFS 只需 O(degree)。

變體題：LC 200 Number of Islands（2D 網格版）、LC 323 Number of Connected Components（鄰接表版）。

理解測驗

🤔 為什麼每次啟動新的 DFS 就代表發現一個新省份？

🤔 這題和 LC 200 Number of Islands 的本質區別是什麼？