资源描述：
《连通图的割点、割边(桥)、块、缩点,有向图的强连通分量》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、连通图的割点、割边(桥)、块、缩点，有向图的强连通分量一、基本概念无向图割点：删掉它之后(删掉所有跟它相连的边)，图必然会分裂成两个或两个以上的子图。块：没有割点的连通子图割边：删掉一条边后，图必然会分裂成两个或两个以上的子图，又称桥。缩点：把没有割边的连通子图缩为一个点，此时满足任意两点间都有两条路径相互可达。求块跟求缩点非常相似，很容易搞混，但本质上完全不同。割点可以存在多个块中(假如存在k个块中)，最终该点与其他点形成k个块，对无割边的连通子图进行缩点后(假设为k个)，新图便变为一棵k个点由k-1条割边连接成的树，倘若其中有一条边不是割边
2、，则它必可与其他割边形成一个环，而能继续进行缩点。有割点的图不一定有割边，如： 3是割点，分别与(1,2)和(4,5)形成两个无割点的块 有割边的图也不定有割点,如： w(1,2)为割边，有向图强连通分量：有向图中任意两点相互可达的连通子图，其实也相当于无向图中的缩点二、算法无向图借助两个辅助数组dfn[],low[]进行DFS便可找到无向图的割点和割边，用一个栈st[]维护记录块和“缩点”后连通子图中所有的点。dfn[i]表示DFS过程中到达点i的时间，low[i]表示能通
3、过其他边回到其祖先的最早时间。low[i]=min(low[i],dfn[son[i]])设v,u之间有边w(v,u)，从v->u： 如果low[u]>=dfn[v],说明v的儿子u不能通过其他边到达v的祖先，此时如果拿掉v,则必定把v的祖先和v的儿子u，及它的子孙分开，于是v便是一个割点，v和它的子孙形成一个块。 如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，
4、则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去，从而第二条无向重边不会被遍历而导致low[u]==dfn[v],而在另外一些问题中，比如电线连接两台设备A,B如果它们之间有两根电线，则应该视为是双连通的，因为任何一条电线出问题都不会破坏A和B之间的连通性，这个时候，我们可以用一个used[]数组标记边的id,DFS时会把一条无向边拆成两条有向边进行遍历,但我们给它们俩同一个id号，在开始遍历v->u前检查它的id是否在上一次u->v时被标记，这样如果两点之间有多条边时，每次遍历都只标记其中一条，还可以通过其他边回去，形成第
5、二条新的路 求割点的时候，维护一个栈st每遍历到一个顶点v则把它放进去，对它的子孙u如果dfn[u]为0，则表示还没有遍历到则先DFS(u),之后再判断low[u]和dfn[v]，如果low[u]>=dfn[v],则把栈中从栈顶到v这一系列元素弹出，这些点与v形成一个块，如果u的子孙x也是一个割点，这样做会不会错把它们和v，u放在一起形成一个块呢，这种情况是不会发生的，如果发现x是一个割点，则DFS到x那一步后栈早就把属于x的子孙弹出来了，而只剩下v,u的子孙，它们之间不存在割点，否则在回溯到v之前也早就提前出栈了！画一个图照着代码模拟一下可
6、以方便理解。 求割边也是一样的。有向图有向图强连通分量的算法有两个，一个是Kosaraju,另一个是Tarjan，前者需要两次DFS，代码量偏大但容易理解，后者只需要一次DFS和维护一个栈便可以，实现简单，详见这里>>强连通分量KosarajuPKTarjan2010-04-2216:23Kosaraju算法对每个不在树中的点开始DFS一次，并记录离开各点的时间，这里是离开的时间，而不是到达时的，比如有图1->22->3则1,2,3分别对应的时间是321,因为3没有出边，所以最先离开，其次是2,最后是1,DFS后，在同一棵树中的点，如果dfn
7、[v]>dfn[u]则说明点从v有可能到达u,而这棵树中的dfn[]最大的点，肯定可以到达每个点，从而在原图的逆图中，每次都选没有访问过的最大的dfn值开始DFS,如果可达点x则说明它们是强连通的voidDFS_T(intu){ inti,v; if(used[u])return; used[u]=1;id[u]=scc; for(i=q[u];i!=-1;i=Tedge[i].pre) { v=Tedge[i].d; if(!used[v])DFS_T(v); }}voidDFS(intv){
8、 inti,u; if(used[v])return; used[v]=1; for(i=p[v];i!=-1;i=edge[i].pr
