1. 用dfs變量，記錄程序調(diào)用了幾次dfs才遍歷完所有的節(jié)點(diǎn)

本來(lái)以為復(fù)雜度是n的，后來(lái)想到每個(gè)點(diǎn)不僅被訪問(wèn)了一次，因?yàn)橐袛噙@個(gè)點(diǎn)是否已經(jīng)訪問(wèn)過(guò)來(lái)

2.可以用并查集結(jié)構(gòu)實(shí)現(xiàn)

只需要遍歷圖中的邊，對(duì)每一條邊，將其左右兩個(gè)端點(diǎn)并為一組

時(shí)間復(fù)雜度是 n*k/2log(n)

k為邊的數(shù)目

對(duì)于圖相關(guān)的算法，通常情況下，遍歷邊比遍歷點(diǎn)要快

總結(jié)

以上是生活随笔為你收集整理的无向图的连通分量的数量的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。