LeetCode 547.省份數(shù)量

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

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

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

給你一個(gè) n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個(gè)城市和第 j 個(gè)城市直接相連，而 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求圖的連通分量

這道題其實(shí)挺裸的，就是讓求一個(gè)圖的連通分量。

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

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

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

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

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

• 時(shí)間復(fù)雜度O(len(isConnected)2)O(len(isConnected)^2)O(len(isConnected)2)。每個(gè)節(jié)點(diǎn)都會被遍歷一次，這個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的所有“連接情況”也會被遍歷一次
• 空間復(fù)雜度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ù)量圖的連通分量的詳細(xì)內(nèi)容，更多關(guān)于C++ LeetCode題解省份數(shù)量的資料請關(guān)注腳本之家其它相關(guān)文章！