求强连通分量tarjan算法

1、For personaluse only in study and research;not for commercial use求强连通分量的tarjan算法强连通分量 ：是有向图中的概念，在一个图的子图中，任意两个点相互可达，也就是存在互通的路径，那么这个子图就是强连通分量。（如果一个有向图的任意两个点相互可达，那么这个图就称为强连通图）。如果 u 是某个强连通分量的根，那么：（1）u 不存在路径可以返回到它的祖先。（2）u 的子树也不存在路径可以返回到u 的祖先。例如：强连通分量。在一个非强连通图中极大的强连通子图就是该图的强连通分量。比如图中子图 1,2,3,5 是一个强连通分量，子图

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

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

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

5、到节点4 ，把 4 加入堆栈。发现节点4 向节点 1 有后向边，节点 1 还在栈中，所以LOW4=1。节点 6 已经出栈， (4,6) 是横叉边，返回 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 算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈， 每条边也只被访问了一次， 所以该算法的时

6、间复杂度为 O(N+M) 。此外，该 Tarjan 算法与求无向图的双连通分量 ( 割点、桥 ) 的 Tarjan 算法也有着很深的联系。学习该 Tarjan 算法，也有助于深入理解求双连通分量的 Tarjan 算法，两者可以类比、组合理解。应用例子：（ OJ 1484 popular cows）题意 ： 有 N只牛，输入 a，b 的话，则说明 b 关注 a, 而且关注有传递性。例如 c 关注 b，且 b 关注 a，则 c 也关注 a。题目问有多少只奶牛能被其他所有的奶牛关注。把题目的模型转换 ：N 个顶点的有向图，有 M 条边。求一共有多少个点，满足这样的条件：所有其它的点都可以到达这个点。

7、这个点满足条件的充要条件是：这个点是树中唯一的出度为 0 的点 。先求强连通分量，然后可以把强连通分量缩成一个点，因为，在强连通分量中的任意两个点可以到达，所有的点具有相同的性质， 即它们分别能到达的点集都是相同的，能够到达它们的点集也是相同的。然后就重新构图，缩点后的图是没有强连通分量的，否则，可将环上所有点也缩成一个点， 与极大强联通分量矛盾。 所以只要找出度为0 的点，并且出度为0 的点只有 1 个 ，如果出度为 0 的点有多个的话，问题则无解。代码：#include#include#define adj 10010#define edg 50010struct nodeint v;in

8、t next;node edgeedg;node edge1edg;int lowadj,dfnadj,Stackadj;int firstadj,first1adj,fuckadj;bool insadj;int 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

9、;insu=true;for(i=firstu;i!=-1;i=edgei.next)v=edgei.v;if(!dfnv)tarjan(v);if(lowulowv)lowu=lowv;else if(insv)if(lowudfnv)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(fi

10、rst);for(k=0;km;k+)建立图scanf(%d%d,&i,&j);edgee.v=j;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

11、;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;icnt;i+)求每个节点的出度for(j=first1i;j!=-1;j=edge1j.next)outdegreei+;sum=num=0;for(i=0;icnt;i+)if(outdegreei=0)求节点为0 的个数sum=cnt_sizei;num+;if(num=1)printf(%dn,sum);elseprintf(0n);return 0;结束！以下无正文仅供个人用于学习、研究；不得用于商业用途。 , .For personal use only in study and research; not for commercial use.Nur f r den pers?nlichen f r Studien, Forschung, zu kommerziell