图论 —— 图的连通性

　

连通图

【基本概念】

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

【算法】

1. 并查集判断连通图：点击这里
2. Kosaraju 算法求强连通分量：点击这里
3. Tarjan 求强连通分量：点击这里
4. Tarjan 缩点：点击这里
5. Tarjan 求割点与桥：点击这里
6. Tarjan 求双连通分量：点击这里
7. 有桥连通图加边变边双连通图：点击这里

【例题】

1.强连通分量

1. 迷宫城堡（HDU-1269）(Tarjan)：点击这里
2. Proving Equivalences（HDU-2767）(缩点)：点击这里
3. equivalent Sets（HDU-3836）(缩点)：点击这里
4. Strongly connected（HDU-4635）(有技巧的缩点)：点击这里
5. Network of Schools（POJ-1236）(Tarjan+缩点)：点击这里
6. The Cow Prom（POJ-3180）(Kosaraju+缩点)：点击这里
7. Hawk-and-Chicken（HDU-3639）(缩点+反向建图)：点击这里

2.割点与桥

1. Network（POJ-1144）(求割点)：点击这里
2. TWO NODES（HDU-4587）(求割点)：点击这里
3. critical Links（LightOJ - 1026）(求桥)：点击这里
4. By Recognizing These Guys, We Find social Networks Useful（HDU-3849）(求桥)：点击这里
5. Caocao's Bridges（HDU-4738）(重边无向图求桥)：点击这里
6. Street Directions（POJ-1515）(无向图求桥+单向边的划分)：点击这里

3.双连通分量

1. Financial Crisis（HDU-3749）(点双连通分量+并查集)：点击这里
2. Road Construction（POJ-3352）(加边变双连通图+缩点)：点击这里
3. redundant Paths（POJ-3177）(加边变双连通图+缩点)：点击这里

相关阅读

Telnet测试端口连通性

如何优雅的使用telnet测试端口连通性 telnet命令是TELNET协议的用户接口，它支持两种模式：命令模式和会话模式，虽然telnet支持许多