---
# System prepended metadata

title: 547. Number of Provinces
tags: [Leetcode]

---

# 547. Number of Provinces

**練習日期：** 2026-02-14
**難度：** Medium
**類型：** Depth-First Search、Graph

## 📘 題目敘述

有 `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`。

## 💻 程式碼實作

```cpp
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);
        }
        return;
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        city.assign(n, false);
        for (int i = 0; i < n; i++) {
            if (!city[i]) {
                connect(i, isConnected);
                provinces++;
            }
        }
        return provinces;
    }
};
```

## 🔗 題目連結
https://leetcode.com/problems/number-of-provinces/description/