1）該圖是強(qiáng)連通的嗎？給定一個(gè)圖G=]VO，VL分別稱為該路徑的起點(diǎn)和終點(diǎn)。t中的邊數(shù)稱為t的長(zhǎng)度。當(dāng)V0=VL時(shí)，路徑稱為循環(huán)。在無(wú)向圖G中，如果頂點(diǎn)VI和VJ之間有一條路，則VI和VJ是連通的。V

1）該圖是強(qiáng)連通的嗎？

給定一個(gè)圖G=]VO，VL分別稱為該路徑的起點(diǎn)和終點(diǎn)。t中的邊數(shù)稱為t的長(zhǎng)度。當(dāng)V0=VL時(shí)，路徑稱為循環(huán)。在無(wú)向圖G中，如果頂點(diǎn)VI和VJ之間有一條路，則VI和VJ是連通的。VI與自身相連。設(shè)d為有向圖。如果通過(guò)省略D中邊的方向而得到的無(wú)向圖是連通圖，則D稱為弱連通或連通。如果D中任意兩個(gè)頂點(diǎn)中至少有一個(gè)可以到達(dá)另一個(gè)頂點(diǎn)，則D稱為單向連通圖。如果D的任意兩個(gè)頂點(diǎn)是相互可達(dá)的，則D稱為強(qiáng)連通圖。從上面的定義中，我們可以很容易地知道有向圖的強(qiáng)連通圖必須是一個(gè)圈，否則它就不能互相連通。連通圖是無(wú)向圖，但不一定是無(wú)向圖。連通分量是指無(wú)向圖中的極連通子圖。有向圖中的最大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。所以我們只需要對(duì)給定的圖進(jìn)行分解。

什么是連通分量？

在無(wú)向圖中，如果存在從頂點(diǎn)VI到頂點(diǎn)VJ的路徑，則VI和VJ是連通的。如果圖中的任意兩個(gè)頂點(diǎn)是連通的，則稱為連通圖。否則，較大的連通子圖稱為連通分量。在有向圖中，如果每對(duì)頂點(diǎn)VI和VJ都有從VI到VJ和從VJ到VI的路徑，則該圖稱為強(qiáng)連通圖；否則，極連通子圖稱為強(qiáng)連通分量。

怎么把有向圖改為無(wú)向圖？

有三種連通分量：邊雙連通分量、點(diǎn)雙連通分量和強(qiáng)連通分量。前兩個(gè)是無(wú)向圖，第二個(gè)是有向圖。這里，我們主要解釋邊雙連通和點(diǎn)雙連通分量雙連通圖：在一個(gè)無(wú)向連通圖中，如果刪除圖的任何一個(gè)節(jié)點(diǎn)都不能改變圖的連通性，那么該圖就是雙連通無(wú)向圖。連通無(wú)向圖是雙連通的當(dāng)且僅當(dāng)它沒(méi)有關(guān)節(jié)。邊雙連通分量：割邊沒(méi)有雙連通分量，刪除原圖的割邊可以得到多個(gè)邊雙連通分量。該算法是tarjan的點(diǎn)疊加算法。點(diǎn)雙連通分量：每個(gè)點(diǎn)雙連通分量都沒(méi)有連接點(diǎn)，同時(shí)原圖的連接點(diǎn)可以存在于多個(gè)雙連通分量中。該算法是tarjan中的邊緣疊加算法。目視檢查的主要問(wèn)題是尖銳。建議完成hihocoder的連通性章節(jié)

，因?yàn)橥耆邢驁D的定義是，對(duì)于它的所有節(jié)點(diǎn)，只有一條有向邊與其他節(jié)點(diǎn)相連。這樣，完全有向圖中的每個(gè)節(jié)點(diǎn)都可以到達(dá)另一個(gè)節(jié)點(diǎn)，因此完全有向圖無(wú)疑是強(qiáng)連通的。