C++?LeetCode0547題解省份數(shù)量圖的連通分量
LeetCode 547.省份數(shù)量
力扣題目鏈接:leetcode.cn/problems/nu…
有 n
個(gè)城市,其中一些彼此相連,另一些沒(méi)有相連。如果城市 a
與城市 b
直接相連,且城市 b
與城市 c
直接相連,那么城市 a
與城市 c
間接相連。
省份 是一組直接或間接相連的城市,組內(nèi)不含其他沒(mé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)給了圖的鄰接矩陣,我們直接對(duì)圖開(kāi)始搜索就好。
初始時(shí),建立一個(gè)布爾類(lèi)型的數(shù)組,數(shù)組長(zhǎng)度為節(jié)點(diǎn)個(gè)數(shù)(len(isConnected)len(isConnected)len(isConnected)),初始值全為falsefalsefalse
然后使用一個(gè)整數(shù)類(lèi)型的變量ansansans來(lái)記錄找到的聯(lián)通分量的個(gè)數(shù),初始值為000
具體思路是:我們遍歷這nnn個(gè)節(jié)點(diǎn),一旦遍歷到某個(gè)節(jié)點(diǎn),就把與這個(gè)節(jié)點(diǎn)相聯(lián)通的所有的節(jié)點(diǎn)遍歷一遍,并把答案數(shù)量加一。
遍歷過(guò)程中,一個(gè)節(jié)點(diǎn)不論是怎么怎么遍歷到的,都需要把布爾數(shù)組中這個(gè)節(jié)點(diǎn)對(duì)應(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)都會(huì)被遍歷一次,這個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的所有“連接情況”也會(huì)被遍歷一次
- 空間復(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ù)量的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C++ 中類(lèi)的拷貝、賦值、銷(xiāo)毀的實(shí)例詳解
這篇文章主要介紹了C++ 中類(lèi)的拷貝、賦值、銷(xiāo)毀的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家,需要的朋友可以參考下2017-09-09C++高精度計(jì)時(shí)的幾種方法總結(jié)(測(cè)試函數(shù)運(yùn)行時(shí)間)
本文介紹了C++中常用的幾種程序計(jì)時(shí)方法,包括clock()函數(shù)、GetTickCount()、QueryPerformanceCounter()以及C++11中的chrono庫(kù)函數(shù),這篇文章主要介紹了C++高精度計(jì)時(shí)的幾種方法,需要的朋友可以參考下2024-09-09一文詳解C++的訪(fǎng)問(wèn)說(shuō)明符
訪(fǎng)問(wèn)說(shuō)明符是 C++ 中控制類(lèi)成員(屬性和方法)可訪(fǎng)問(wèn)性的關(guān)鍵字,它們用于封裝類(lèi)數(shù)據(jù)并保護(hù)其免受意外修改或?yàn)E用,本文將給大家詳細(xì)的介紹一下C++的訪(fǎng)問(wèn)說(shuō)明符,感興趣的朋友可以參考下2024-04-04對(duì)C++默認(rèn)構(gòu)造函數(shù)的一點(diǎn)重要說(shuō)明
下面小編就為大家?guī)?lái)一篇對(duì)C++默認(rèn)構(gòu)造函數(shù)的一點(diǎn)重要說(shuō)明。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12詳解如何配置CLion作為Qt5開(kāi)發(fā)環(huán)境的方法
這篇文章主要介紹了詳解如何配置CLion作為Qt5開(kāi)發(fā)環(huán)境的方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04QTimer與QTime實(shí)現(xiàn)電子時(shí)鐘
這篇文章主要為大家詳細(xì)介紹了QTimer與QTime實(shí)現(xiàn)電子時(shí)鐘,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-07-07