欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++?LeetCode0547題解省份數(shù)量圖的連通分量

 更新時(shí)間:2022年12月16日 10:36:14   作者:LetMeFly  
這篇文章主要為大家介紹了C++?LeetCode0547題解省份數(shù)量圖的連通分量示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

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]10
  • 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í)例詳解

    這篇文章主要介紹了C++ 中類(lèi)的拷貝、賦值、銷(xiāo)毀的實(shí)例詳解的相關(guān)資料,希望通過(guò)本文能幫助到大家,需要的朋友可以參考下
    2017-09-09
  • C++高精度計(jì)時(shí)的幾種方法總結(jié)(測(cè)試函數(shù)運(yùn)行時(shí)間)

    C++高精度計(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ō)明符

    一文詳解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ō)明

    對(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)境的方法

    這篇文章主要介紹了詳解如何配置CLion作為Qt5開(kāi)發(fā)環(huán)境的方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2021-04-04
  • DEVC++實(shí)現(xiàn)推箱子小游戲

    DEVC++實(shí)現(xiàn)推箱子小游戲

    這篇文章主要為大家詳細(xì)介紹了DEVC++實(shí)現(xiàn)推箱子小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-01-01
  • QTimer與QTime實(shí)現(xiàn)電子時(shí)鐘

    QTimer與QTime實(shí)現(xiàn)電子時(shí)鐘

    這篇文章主要為大家詳細(xì)介紹了QTimer與QTime實(shí)現(xiàn)電子時(shí)鐘,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-07-07
  • 詳解C/C++如何發(fā)送與接收Kafka消息

    詳解C/C++如何發(fā)送與接收Kafka消息

    系統(tǒng)之間通信方式很多如:系統(tǒng)之間調(diào)用(http/rpc等),異步間接調(diào)用如發(fā)送消息、公共存儲(chǔ)等,算法工程為C/C++工程,本文將介紹如何在C/C++中如何發(fā)送與接收Kakfa消息(包含:Kafka的SASL認(rèn)證方式),并提供了詳細(xì)的源碼和講解,需要的朋友可以參考下
    2024-07-07
  • 帶你粗略了解c++的最大乘積

    帶你粗略了解c++的最大乘積

    這篇文章主要為大家詳細(xì)介紹了C++的最大乘積,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能給你帶來(lái)幫助
    2021-08-08
  • C++輸出問(wèn)題:保留兩位小數(shù)

    C++輸出問(wèn)題:保留兩位小數(shù)

    這篇文章主要介紹了C++輸出問(wèn)題:保留兩位小數(shù)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-11-11

最新評(píng)論