求强连通分量tarjan算法

1、求强连通分量的tarjan算法强连通分量：是有向图中的概念，在一个图的子图中，任意两个点相互可达，也就是存在互通的路径，那么这个子图就是强连通分量。（如果一个有向图的任意两个点相互可达，那么这个图就称为强连通图）。如果u是某个强连通分量的根，那么：（1）u不存在路径可以返回到它的祖先。（2）u的子树也不存在路径可以返回到u的祖先。· 例如：· 强连通分量。在一个非强连通图中极大的强连通子图就是该图的强连通分量。比如图中子图1,2,3,5是一个强连通分量，子图4是一个强连通分量。tarjan算法的基础是深度优先搜索，用两个数组low和dfn，和一个栈。low数组是一个标记数组

2、，记录该点所在的强连通子图所在搜索子树的根节点的dfn值，dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。根据以下几条规则，经过搜索遍历该图和对栈的操作，我们就可以得到该有向图的强连通分量。算法规则：· 数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。· 堆栈：每搜索到一个点，将它压入栈顶。· 当点p有与点p相连时，如果此时（时间为dfnp时）p不在栈中，p的low值为两点的low值中较小的一个。· 当点p有与点p相连时，如果此时（时间为dfnp时）p在栈中，p的low值为p的low值和p的dfn值中较小的一个。

3、83; 每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。· 继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。算法伪代码：tarjan(u)DFNu=Lowu=+Index / 为节点u设定次序编号和Low初值Stack.push(u) / 将节点u压入 栈中for each (u, v) in E / 枚举每一条边if (！dfnv) / 如果节点v未被访问过tarjan(v) / 继续向下找Lowu = min(Lowu, Lowv)else

4、 if (v in S) / 如果节点v还在栈内Lowu = min(Lowu, DFNv)if (DFNu = Lowu) / 如果节点u是强连通分量的根dov = S.pop / 将v退栈，为该强连通分量中一个顶点while(u = v);演示算法流程；从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN6=LOW6，找到了一个强连通分量。退栈到u=v为止，6为一个强连通分量。返回节点5，发现DFN5=LOW5，退栈后5为一个强连通分量。返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW4=1。节点6已经出栈，(4,6)是横

5、叉边，返回3，(3,4)为树枝边，所以LOW3=LOW4=1。继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW2=DFN4=5。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一个连通分量1,3,4,2。经过该算法，求出了图中全部的三个强连通分量1,3,4,2,5,6。可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的T

6、arjan算法，两者可以类比、组合理解。应用例子：（OJ 1484 popular cows）题意：有N只牛，输入a，b的话，则说明b关注a,而且关注有传递性。例如c关注b，且b关注a，则c也关注a。题目问有多少只奶牛能被其他所有的奶牛关注。把题目的模型转换：N个顶点的有向图，有M条边。求一共有多少个点，满足这样的条件：所有其它的点都可以到达这个点。这个点满足条件的充要条件是：这个点是树中唯一的出度为0的点。先求强连通分量，然后可以把强连通分量缩成一个点，因为，在强连通分量中的任意两个点可以到达，所有的点具有相同的性质，即它们分别能到达的点集都是相同的，能够到达它们的点集也是相同的。然后就重新

7、构图，缩点后的图是没有强连通分量的，否则，可将环上所有点也缩成一个点，与极大强联通分量矛盾。所以只要找出度为0的点，并且出度为0的点只有1个 ，如果出度为0的点有多个的话，问题则无解。代码：#include<stdio.h>#include<string.h>#define adj 10010#define edg 50010struct nodeint v;int next;node edgeedg;node edge1edg;int lowadj,dfnadj,Stackadj;int firstadj,first1adj,fuckadj;bool insadj;i

8、nt n,m,temp,cnt,top,count;int cnt_sizeadj,belongadj,outdegreeadj;void creat(int u,int v) edge1count.next=first1u;edge1count.v=v;first1u=count+;void tarjan(int u)int i,v;dfnu=lowu=+temp;Stacktop+=u;insu=true;for(i=firstu;i!=-1;i=edgei.next)v=edgei.v;if(!dfnv)tarjan(v);if(lowu>lowv)lowu=lowv;else i

9、f(insv)if(lowu>dfnv)lowu=dfnv;if(dfnu=lowu)int j;dotop-;j=Stacktop;insj=false;cnt_sizecnt+;belongj=cnt;while(u!=j);cnt+;int main()int i,j,k,v,sum,num;int e=0;scanf("%d%d",&n,&m); memset(first,-1,sizeof(first);for(k=0;k<m;k+) 建立图scanf("%d%d",&i,&j);edgee.v=j;

10、edgee.next=firsti;firsti=e;e+; memset(dfn,0,sizeof(dfn);memset(ins,false,sizeof(ins);temp=cnt=top=0;memset(cnt_size,0,sizeof(cnt_size);memset(low,0,sizeof(low);for(i=1;i<=n;i+) 求强连通分量if(!dfni)tarjan(i);memset(first1,-1,sizeof(first1);count=0;for(i=1;i<=n;i+) 重新构造图for(j=firsti;j!=-1;j=edgej.next)v=edgej.v;if(belongi!=belongv)creat(belongi,belongv);memset(outdegree,0,sizeof(outdegree);for(i=0;i<cnt;i+) 求每个节点的出度for(j=first1i;j!=-1;j=edge1j.ne