【基本概念】

1.連通圖與連通分量

1）連通圖：無向圖 G 中，若對任意兩點，從頂點 Vi 到頂點 Vj 有路徑，則稱 Vi 和 Vj 是連通的，圖 G 是一連通圖

2）連通分量：無向圖 G 的連通子圖稱為 G 的連通分量

? ? 任何連通圖的連通分量只有一個，即其自身，而非連通的無向圖有多個連通分量

? ??

? ? 以上圖為例，總共有四個連通分量，分別是：ABCD、E、FG、HI。

2.強連通圖與強連通分量

1）強連通圖：有向圖 G 中，若對任意兩點，從頂點 Vi 到頂點 Vj，都存在從?Vi 到?Vj 以及從 Vj 到 Vi 的路徑，則稱 G 是強連通圖

2）強連通分量：有向圖 G 的強連通子圖稱為 G 的強連通分量

? ? 強連通圖只有一個強連通分量，即其自身，非強連通的有向圖有多個強連通分量。?

? ??

? ? 以上圖為例，總共有三個強連通分量，分別是：abe、fg、cdh

【算法】

并查集判斷連通性：點擊這里

Floyd 計算傳遞閉包：點擊這里

Kosaraju 算法求強連通分量：點擊這里

Tarjan 求強連通分量：點擊這里

Tarjan 縮點：點擊這里

Tarjan 求割點與橋：點擊這里

Tarjan 求雙連通分量：點擊這里

有橋連通圖加邊變邊雙連通圖：點擊這里

【例題】

1.連通性判斷

刻錄光盤（信息學奧賽一本通-T1383）(Floyd 判斷連通性)：點擊這里

Wireless Network（POJ-2236）(并查集判斷連通性)：點擊這里

2.傳遞閉包

Cow Contest（POJ-3660 ）(傳遞閉包)：點擊這里

Ranking the Cows（POJ-3275 ）(傳遞閉包)：點擊這里

珍珠（信息學奧賽一本通-T1384）(傳遞閉包)：點擊這里

Dima and Bacteria（CF-400D）(傳遞閉包+并查集)：點擊這里

3.強連通分量

迷宮城堡（HDU-1269）(Tarjan)：點擊這里

Proving Equivalences（HDU-2767）(縮點)：點擊這里

Equivalent Sets（HDU-3836）(縮點)：點擊這里

Islands（2017 ACM-ICPC 亞洲區(烏魯木齊賽區)網絡賽 F）(縮點)：點擊這里

Strongly connected（HDU-4635）(有技巧的縮點)：點擊這里

Network of Schools（POJ-1236）(Tarjan+縮點)：點擊這里

The Cow Prom（POJ-3180）(Kosaraju+縮點)：點擊這里

Hawk-and-Chicken（HDU-3639）(縮點+反向建圖)：點擊這里

4.割點與橋

Network（POJ-1144）(求割點)：點擊這里

TWO NODES（HDU-4587）(求割點)：點擊這里

Critical Links（LightOJ - 1026）(求橋)：點擊這里

By Recognizing These Guys, We Find Social Networks Useful（HDU-3849）(求橋)：點擊這里

Caocao's Bridges（HDU-4738）(重邊無向圖求橋)：點擊這里

Street Directions（POJ-1515）(無向圖求橋+單向邊的劃分)：點擊這里

5.雙連通分量

Financial Crisis（HDU-3749）(點雙連通分量+并查集)：點擊這里

Road Construction（POJ-3352）(加邊變雙連通圖+縮點)：點擊這里

Redundant Paths（POJ-3177）(加邊變雙連通圖+縮點)：點擊這里

總結

以上是生活随笔為你收集整理的图论 —— 图的连通性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。