547. Number of Provinces

📘 題目敘述

有 n 個城市。有些城市彼此相連，有些則沒有。

如果城市 a 和城市 b 直接相連，且城市 b 和城市 c 直接相連，那麼城市 a 和城市 c 就是間接相連。

一個省份（province）是一組彼此直接或間接相連的城市，而且省份之外不包含其他城市。

給你一個 n x n 的矩陣 isConnected，其中：

• 若第 i 個城市與第 j 個城市直接相連，則 isConnected[i][j] = 1
• 否則 isConnected[i][j] = 0

請回傳省份的總數量。

條件限制

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 是 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

🧠 解題思路

我把題目當成一張圖：

• 城市是點
• isConnected[i][j] == 1 代表 i 和 j 之間有邊

題目要的「省份數」其實就是圖中「連通分量」的數量。

所以我的作法是：

• 用 city 記錄每個城市有沒有被走過（visited）
• 從第 0 個城市一路掃到第 n-1 個城市
• 只要遇到一個還沒走過的城市，代表我找到一個新的省份起點
• 從它開始做 DFS，把同一個省份裡所有能連到的城市都標記成 visited
• DFS 結束後，省份數 provinces 加 1

所有變數

• city：vector<bool>，city[x] = true 代表城市 x 已經被 DFS 走過
• provinces：省份數量（每找到一個新的連通分量就加一）
• n：城市總數（isConnected.size()）

🪜 主要流程步驟

1. 用 city 當作 visited，避免重複走城市

我先把 city 全部設成 false，代表每個城市一開始都還沒被走過。

之後 DFS 走到一個城市時就把它設成 true，保證每個城市最多被處理一次。

2. connect(i) 用 DFS 把同一個省份全部標記起來

connect(i, isConnected) 的意思是：從城市 i 出發，把所有「直接或間接相連」的城市都找出來。

流程是：

• 先把 city[i] = true
• 掃描同一列 isConnected[i][*]
• 只要發現某個城市 j 與 i 相連，且 city[j] 還是 false
• 就遞迴呼叫 connect(j, isConnected) 繼續擴張這個省份

這樣 DFS 結束時，整個連通分量都會被標成 visited。

3. 主迴圈掃所有城市，遇到沒走過的就代表新省份

在 findCircleNum 裡，我從 0 ~ n-1 逐一檢查：

• 如果 city[i] 是 false，代表這個城市還不屬於任何已探索過的省份
• 我就從它開始 connect(i, isConnected)，把整個省份一次走完
• 然後 provinces++

最後回傳 provinces。

⏱️ 複雜度

• 時間複雜度：O(n^2)，因為對每個城市做 DFS 時，核心操作是掃描一整列 isConnected[i][0..n-1]。
• 空間複雜度：O(n)，city 需要 n，遞迴深度最壞也可能到 n。

💻 程式碼實作

class Solution {
public:
    vector<bool> city;
    int provinces = 0;
    int n;

    void connect(int i, vector<vector<int>>& v) {
        city[i] = true;
        for (int j = 0; j < n; j++) {
            if (v[i][j] && !city[j]) {
                connect(j, v);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        city.assign(n, false);
        provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!city[i]) {
                connect(i, isConnected);
                provinces++;
            }
        }

        return provinces;
    }
};

🔗 題目連結

https://leetcode.com/problems/number-of-provinces/