有向图强连通分量的Tarjan算法

1、有向图强连通分量的Tarjan算法有向图强连通分量在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。下图中，子图1,2,3,4为一个强连通分量，因为顶点1,2,3,4两两可达。5,6也分别是两个强连通分量。直接根据定义，用双向遍历取交集的方法求强连通分量，时间复杂度为O(N2+M)。更好的方法是Kosaraju算法或Tarjan算法，两者的时间复杂度都是O(N+M)。本文介绍的

2、是Tarjan算法。Tarjan算法Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。定义DFN(u)为节点u搜索的次序编号(时间戳)，Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。由定义可以得出，Low(u)=Min DFN(u), Low(v),(u,v)为树枝边，u为v的父节点 DFN(v),(u,v)为指向栈中节点的后向边(非横叉边)当DFN(u)=Low(u)时，以u为根的搜索子树上所有节点是一个强连通分量。算法伪代码如下tarjan(u

3、) DFNu=Lowu=+Index / 为节点u设定次序编号和Low初值 Stack.push(u) / 将节点u压入栈中 for each (u, v) in E / 枚举每一条边 if (v is not visted) / 如果节点v未被访问过 tarjan(v) / 继续向下找 Lowu = min(Lowu, Lowv) else if (v in S) / 如果节点v还在栈内 Lowu = min(Lowu, DFNv) if (DFNu = Lowu) / 如果节点u是强连通分量的根 repeat v = S.pop / 将v退栈，为该强连通分量中一个顶点 print v un

4、til (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)是横叉边，返回3，(3,4)为树枝边，所以LOW3=LOW4=1。继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW2=DFN4=5。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一

5、个连通分量1,3,4,2。至此，算法结束。经过该算法，求出了图中全部的三个强连通分量1,3,4,2,5,6。可以发现，运行Tarjan算法的过程中，每个顶点都被访问了一次，且只进出了一次堆栈，每条边也只被访问了一次，所以该算法的时间复杂度为O(N+M)。求有向图的强连通分量还有一个强有力的算法，为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法，其时间复杂度也是O(N+M)。与Trajan算法相比，Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS，不用建立逆图，更简洁。在实际的测试中，Tarjan算法的运行效率也比Kosaraju算

6、法高30%左右。此外，该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法，也有助于深入理解求双连通分量的Tarjan算法，两者可以类比、组合理解。求有向图的强连通分量的Tarjan算法是以其发明者Robert Tarjan命名的。Robert Tarjan还发明了求双连通分量的Tarjan算法，以及求最近公共祖先的离线Tarjan算法，在此对Tarjan表示崇高的敬意。附：tarjan算法的C+程序void tarjan(int i) int j; DFNi=LOWi=+Dindex; instacki=true; Stap+Stop

7、=i; for (edge *e=Vi;e;e=e-next) j=e-t; if (!DFNj) tarjan(j); if (LOWjLOWi) LOWi=LOWj; else if (instackj & DFNjLOWi) LOWi=DFNj; if (DFNi=LOWi) Bcnt+; do j=StapStop-; instackj=false; Belongj=Bcnt; while (j!=i); void solve() int i; Stop=Bcnt=Dindex=0; memset(DFN,0,sizeof(DFN); for (i=1;i=N;i+) if (!DFN

8、i) tarjan(i);例1、/p/1595 /problem?id=1236分析：题目大意：N(2N100)各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。2，至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。也就是：给定一个有向图，求：1)至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点2)至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶

9、点顶点数= 100解题思路：1.求出所有强连通分量2.每个强连通分量缩成一点，则形成一个有向无环图DAG。3. DAG上面有多少个入度为0的顶点，问题1的答案就是多少在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少加边的方法：要为每个入度为0的点添加入边，为每个出度为0的点添加出边假定有n个入度为0的点，m个出度为0的点，如何加边？把所有入度为0的点编号0,1,2,3,4 .N -1每次为一个编号为i的入度0点可达的出度0点，添加一条出边，连到编号为(i+1)%N的那个出度0点,这需要加n条边若m n，则还有m-n个入度0点，则从这些点以外任取一点，和这些点都连上边，即可

10、，这还需加m-n条边。所以，max(m,n)就是第二个问题的解此外：当只有一个强连通分支的时候，就是缩点后只有一个点，虽然入度出度为0的都有一个，但是实际上不需要增加清单的项了，所以答案是1，0；一句话：强连通分量缩点求入度为0的个数和出度为0的分量个数提示：缩点，并不是真的新建一个图，只是对同一个强连通分量涂一种颜色即可。参考程序：#include #include #include #include #include using namespace std;const int maxn=10000;int premaxn,lowlinkmaxn,sccnomaxn,dfsclock,scc

11、cnt;vectorGmaxn;stackS;int n;void tarjan(int u) preu=lowlinku=+dfsclock; S.push(u); for(int i=0;iGu.size();i+) int v=Gui; if(!prev) dfs(v); lowlinku=min(lowlinku,lowlinkv); else if(!sccnov)lowlinku=min(lowlinku,prev); if(lowlinku=preu) scccnt+; for(;) int x=S.top(); S.pop(); sccnox=scccnt; if(x=u)br

12、eak; void find(int n) dfsclock=scccnt=0; memset(sccno,0,sizeof(sccno); memset(pre,0,sizeof(pre); for(int i=0;in; for(int i=0;ia&a!=0) Gi.push_back(a-1); find(n); int in0maxn,out0maxn; for(int i=1;i=scccnt;i+)in0i=out0i=1; for(int u=0;un;u+) for(int u=0;un;u+) for(int i=0;iGu.size();i+) int v=Gui; if

13、(sccnou!=sccnov)in0sccnov=out0sccnou=0; int a=0,b=0; int ans1,ans2; for(int i=1;i=scccnt;i+) if(in0i)a+; if(out0i)b+; ans2=max(a,b); if(scccnt=1)a=1,ans2=0; coutaendl; coutans2endl; return 0;例2、/p/1626 该题数据范围：n=1000,m=10000解题报告：首先直接跑一下tarjan。强连通分量（注：不包括单独一个点）的数量就是第一问的答案。接下来回答第二问。可以进行

14、暴力缩点（新建图，并记录出度）。然后你就会神奇的发现一个很神奇的地方。出度为0的点所在的强连通分量（且只有一个联通分量）就是答案。这时你输出这个强连通分量即可。注意，若该强连通分量是一个点，就输出-1。参考程序：#include #include #include #include using namespace std;const int MAX_N = 1005, MAX_M = 10005;struct node int v, next; EMAX_M;int headMAX_N, top = 0;inline void add(int u, int v) E+ top.v = v; E

15、top.next = headu; headu = top;int n, m;void init() scanf(%d%d,&n,&m); for (int i = 1; i = m; i +) int u, v; scanf(%d%d,&u,&v); add(u, v); int dfnMAX_N, lowMAX_N, staMAX_N, Tm = 0, scc = 0, ouMAX_N, sz = 0;int colMAX_N, numMAX_N;bool visMAX_N, inqMAX_N;void tarjan(int x) sta+sz = x; inqx = visx = 1;

16、lowx = dfnx = + Tm; for (int i = headx; i; i = Ei.next) if (!visEi.v) tarjan(Ei.v); lowx = min(lowx, lowEi.v); else if (inqEi.v) lowx = min(lowx, dfnEi.v); if (dfnx = lowx) int now; scc +; do numscc +; now = stasz -; inqnow = 0; colnow = scc; while (now != x); void doit() memset(vis, 0, sizeof(vis);

17、 for (int i = 1; i = n; i +) if (!visi) tarjan(i); for (int i = 1; i = n; i +) for (int j = headi; j; j = Ej.next) if (coli != colEj.v) oucoli +; int cnt = 0, po, ans = scc; for (int i = 1; i = scc; i +) if (!oui) cnt +, po = i; if (numi = 1) ans -; printf(%dn, ans); if (cnt = 1) if (numpo = 1) printf(-1n); else for (int i = 1