[Tarjan系列] Tarjan算法与有向图的SCC
前面的文章介绍了如何用Tarjan算法计算无向图中的e-DCC和v-DCC以及如何缩点。
本篇文章资料参考：李煜东《算法竞赛进阶指南》
这一篇我们讲如何用Tarjan算法求有向图的SCC( 强连通分量 )已经如何缩点。
给定一张有向图，若对于图中任意两个节点x和y，
既有x到y的路径，又有y到x的路径，则该有向图是一张“强连通图”。
有向图的极大连通子图被称为“强连通分量”，即SCC。
一个环一定是强连通图。如果既有x到y的路径，又有y到x的路径，那么x和y就一定在一个环中。
这就是Tarjan算法的原理：对于每个点x，找到与它一起能构成环的所有点。
下面介绍有向图中的三种边(x,y)：
1. 树枝边：搜索树中x是y的父节点
2. 前向边：搜索树中x是y的祖先节点
3. 后向边：搜索树中y是x的祖先节点
4. 横叉边：除了以上三种情况外的边，满足dfn[y]<dfn[x]
这里只给出简单定义，不再赘述。
我们可以发现，用Tarjan算法求SCC时，后向边(x,y)可以和搜索树上从y到x的路径构成一个环。
除后向边外，通过横叉边也可能找到一条从y出发能回到x的祖先节点的路径。
那么为了找到通过横叉边和后向边构成的环，Tarjan算法在dfs的过程中维护一个栈，当访问到节点x时，栈中需要保存以下两类节点：
1. 搜索树上x的祖先节点，记为集合anc(x)。设y∈anc(x)，若存在一条后向边(x,y)，则(x,y)和y到x之间的路径一起形成环。
2. 已经访问过，并且存在一条路径到达anc(x)的节点。
设z时一个这样的点，从z出发存在一条路径到达y∈anc(x)。若存在横叉边(x,y)，则(x,z)、z到y的路径、y到x的路径形成一个环。
综上，栈中的节点就是能从x出发点的“后向边”和“横叉边”形成环的节点。
至此，我们引入追溯值low[x]的概念，有向图的Tarjan算法里面的定义和无向图是不一样的。
还是设subtree(x)表示以x为根的子树。x的追溯值low[x]定义为满足一下条件的节点的最小dfn：
1. 该点在栈中 2. 存在一条从subtree(x)出发的有向边，以该点为终点
根据以上定义，Tarjan算法根据以下步骤计算low[x]：
1. 当节点x第一次被访问时，将x入栈，初始化low[x]=dfn[x]
2. 扫描从头x出发的每条边(x,y)，若y没被访问过，则说明(x,y)时树枝边，递归访问y，从y回溯之后，令low[x]=min(low[x],low[y])，若y被访问过且y在栈中，令low[y]=min(low[x],dfn[y])
3. 从x回溯之前，判断是否有low[x]=dfn[x]，若成立，则不断从栈中弹出节点直至x出栈。
SCC的判定法则：
在上面的计算步骤3中，从栈中从x到栈顶的所有节点构成一个SCC。
少废话，上代码！
好der~
#include<bits/stdc++.h> #define N 1000010 using namespace std; inline int read(){ int data=0,w=1;char ch=0; while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar(); return data*w; } struct Edge{ int nxt,to; #define nxt(x) e[x].nxt #define to(x) e[x].to }e[N<<1]; int head[N],tot=1; inline void addedge(int f,int t){ nxt(++tot)=head[f];to(tot)=t;head[f]=tot; } int dfn[N],low[N],stk[N],ins[N],c[N]; vector<int> scc[N]; int n,m,cnt,top,num; void tarjan(int x){ dfn[x]=low[x]=++cnt; stk[++top]=x,ins[x]=1; for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]);//搜索树上的点 }else if(ins[y]) low[x]=min(low[x],dfn[y]);//y在栈中且y被访问过了 if(dfn[x]==low[x]){ num++;int z;//新的一个SCC do{ z=stk[top--],ins[z]=0;//弹出栈顶元素z c[z]=num,scc[num].push_back(z);//z插入存第num个SCC的vector里 }while(z!=x);//知道x被弹出栈 } } } int main(){ n=read();m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); addedge(x,y); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=num;i++){ printf("%d:",i); for(int j=0;j<scc[i].size();j++){ printf(" %d",scc[i][j]); } putchar(10); } return 0; }
SCC的缩点就非常简单了，上面我们已经用c[x]储存了每个点所在的SCC的编号，那我们直接类似e-DCC的缩点，把每个SCC缩成一个点，若c[x]≠c[y]，我们就在编号为c[x]和c[y]的SCC中连一条边就可以得到一个有向无环图( DAG )。
代码真的非常简单，甚至不需要再跑一遍dfs。
给出代码：
for(int x=1;x<=n;x++) for(int i=head[x];i;i=nxt(i)){ int y=to(i); if(c[x]==c[y])continue; addedge_c(c[x],c[y]); } //够简单了吧...
整个程序的代码我就不贴出来了，建新图和我前面e-DCC缩点的博客完全一致。
下一篇讲点数学，别忘了来听课。