Leetcode 547 省份數量

問題重述

有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那麼城市 a 與城市 c 間接相連。

省份 是一組直接或間接相連的城市，組内不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

傳回矩陣中 省份 的數量。

示例 1：

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]

輸出：2

思路

深度優先搜尋。這一題和695相似，我們看清題目，本題有n個人也就是n個節點，一個節點有n條邊。表示和每個省份的關系。

是以我們按照省份，一個一個搜尋即可。如果它是省份中的一個，count加一，并且用visited數組記錄标記這個城市，可以看代碼不多做解釋。

最終代碼

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size(), count = 0;
        vector<bool> visited(n, false);//一個人最多有n條邊，表示和所有人都是朋友
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(isConnected, i, visited);
                ++count;
            }
        }
        return count;
    }
    void dfs(vector<vector<int>>& isConnected, int i, vector<bool>& visited) {
        visited[i] = true;//隻需要一行一行掃過去，如果發現有好友就變1，後續比如[0,1][1,0]是好友，第一遍掃描[0,1]，已經将visited[0]歸為true，後續掃描[1,0]的時候，隻需要判斷visited[k]即可，如果為真說明一個判斷過這個人
        for (int k = 0; k < isConnected.size(); ++k) {
            if (isConnected[i][k] == 1 && !visited[k]) {
                dfs(isConnected, k, visited);
            }
        }
    }
};