Tarjan算法 求解有向图强连通分量
一.算法简介
Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法,它能做到线性时间的复杂度。
我们定义:
如果两个顶点可以相互通达,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。
例如:在上图中,{1 , 2 , 3 , 4 } , { 5 } , { 6 } 三个区域可以相互连通,称为这个图的强连通分量。
Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
再Tarjan算法中,有如下定义。
DFN[ i ] : 在DFS中该节点被搜索的次序(时间戳)
LOW[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号
当DFN[ i ]==LOW[ i ]时,为i或i的子树可以构成一个强连通分量。
伪代码:
tarjan(u){
DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
Stack.push(u) // 将节点u压入栈中
for each (u, v) in E // 枚举每一条边
if (v is not visted) // 如果节点v未被访问过
tarjan(v) // 继续向下找
Low[u] = min(Low[u], Low[v])
else if (v in S) // 如果节点u还在栈内
Low[u] = min(Low[u], DFN[v])
if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
repeat v = S.pop // 将v退栈,为该强连通分量中一个顶点
print v
until (u== v)
}
图示代码执行过程
代码:1
void Tarjan ( int x ) {//代表第几个点在处理,递归的是点
dfn[ x ] = ++dfs_num ;//新进点的初始化
low[ x ] = dfs_num ;
vis [ x ] = true ;//表示在栈中
stack [ ++top ] = x ; //进栈
for ( int i=head[ x ] ; i!=0 ; i=e[i].next ){
int temp = e[ i ].to ;
if ( !dfn[ temp ] ){//如果没有访问过
Tarjan ( temp ) ; //往下延申,开始递归
low[ x ] = min ( low[ x ] , low[ temp ] ) ; //递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,
//涉及到强连通分量子树最小根的事情。
}
else if ( vis[ temp ])//如果访问过,并且还在栈里。
{
low[ x ] = min ( low[ x ] , dfn[ temp ] ) ;//比较谁是谁的儿子/父亲。就是链接对应关系
}
}
if ( dfn[ x ]==low[ x ] ) {//构成强连通分量
vis[ x ] = false ;
color[ x ] = ++col_num ;//染色
while ( stack[ top ] != x ) {//清空
color [stack[ top ]] = col_num ;
vis [ stack[ top-- ] ] = false ;
}
top -- ;
}
}
tarjan一遍不能搜完所有的点,因为存在孤立点或者其他
所以我们要对一趟跑下来还没有被访问到的点继续跑tarjan
怎么知道这个点有没有被访问呢?
看看它的dfn是否为0!
for(int i=1;i<=n;i++)
if(!DFN[i]) tarjan(i);//当这个点没有访问过,就从此点开始。防止图没走完
例题:
http://icpc.upc.edu.cn/problem.php?cid=1740&pid=6
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxm=1e3+5;
int head[maxn],nume;
struct edge
{
int v,next;
}e[maxm];
void add_edge(int u,int v)
{
e[nume].v=v;
e[nume].next=head[u];
head[u]=nume++;
}
int dfn[maxn],low[maxn],tot;
int ans;
int sta[maxn],top;
bool insta[maxn];
void Tarjan(int u)
{
dfn[u]=low[u]=++tot;
sta[top++]=u;
insta[u]=1;
for(int i=head[u];i>=0;i=e[i].next)
{
int v=e[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else
{
if(insta[v])
{
low[u]=min(low[u],dfn[v]);
}
}
}
if(low[u]==dfn[u])
{
ans++;
while(top)
{
int v=sta[--top];
insta[v]=0;
if(u==v)
break;
}
}
}
int n,m;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(head,-1,sizeof head);
memset(dfn,0,sizeof(dfn));
tot=top=ans=nume=0;
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
add_edge(u+1,v+1);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
Tarjan(i);
}
cout<<ans<<endl;
}
return 0;
}