LeetCode 547.省份數(shù)量

力扣題目鏈接：leetcode.cn/problems/nu…

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

省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。

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

返回矩陣中 省份 的數(shù)量。

示例 1：

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

示例 2：

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

提示：

• 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]

方法一：BFS求圖的連通分量

這道題其實挺裸的，就是讓求一個圖的連通分量。

題目中，已經(jīng)給了圖的鄰接矩陣，我們直接對圖開始搜索就好。

初始時，建立一個布爾類型的數(shù)組，數(shù)組長度為節(jié)點個數(shù)（len(isConnected)len(isConnected)len(isConnected)），初始值全為falsefalsefalse

然后使用一個整數(shù)類型的變量ansansans來記錄找到的聯(lián)通分量的個數(shù)，初始值為000

具體思路是：我們遍歷這nnn個節(jié)點，一旦遍歷到某個節(jié)點，就把與這個節(jié)點相聯(lián)通的所有的節(jié)點遍歷一遍，并把答案數(shù)量加一。

遍歷過程中，一個節(jié)點不論是怎么怎么遍歷到的，都需要把布爾數(shù)組中這個節(jié)點對應的布爾值標記為truetruetrue（表示該點已遍歷）

• 時間復雜度O(len(isConnected)2)O(len(isConnected)^2)O(len(isConnected)2)。每個節(jié)點都會被遍歷一次，這個節(jié)點與其他節(jié)點的所有“連接情況”也會被遍歷一次
• 空間復雜度O(len(isConnected))O(len(isConnected))O(len(isConnected))

AC代碼

C++

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                queue<int> q;
                q.push(i);
                ans++;
                while (q.size()) {
                    int thisNode = q.front();
                    q.pop();
                    for (int to = 0; to < n; to++) {
                        if (isConnected[thisNode][to] && !visited[to]) {
                            visited[to] = true;
                            q.push(to);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

以上就是C++ LeetCode0547題解省份數(shù)量圖的連通分量的詳細內(nèi)容，更多關于C++ LeetCode題解省份數(shù)量的資料請關注腳本之家其它相關文章！

最新評論