Tarjan模板 - #include <Seter> - using namespace Orz;

Tarjan模板

Seter posted @ 2012年1月22日 15:35 in Practice with tags SCC , 1810 阅读

相当经典的算法。以前都是背模板的,现在打算较深刻地理解一下……

大致思想:遍历到点x时,在栈中的点是有可能与x组成SCC的点。如果x及其子树能够直接访问到的在栈中的DFS序最小的点是x,则x是一个强连通分量在DFS树中的根。每处理完一个根及其子树的信息,就输出此SCC。

对每个节点记录四样东西:DFS序(T),访问标记,栈标记,节点及其子树能够直接访问到的在栈中的DFS序最小的点的DFS序(L)。访问标记这个可以和DFS序合并,比如DFS序从1开始,那么所有DFS序为0的点就是未访问过的点。

线性时间复杂度的保证在于,每个点最多访问一次,进出栈一次。


假设我们在点x上,初始Lx=Tx。有一条x->y的边,分三类讨论。

1.y未访问,则y一定不在栈中。这说明在DFS树中,y是x的儿子。DFS处理y的信息后Lx=min(Lx,Ly)。

2.y不在栈中,已访问。这说明从y遍历下来的时候没有遍历到x,y已经被分到另一个SCC中了。就是说,虽然x->y,但是y-/>x。x和y不可能在同一个SCC中。Because node y has been visited, nothing should be done。

3.y在栈中,已访问。这说明y->x,x->y,x和y应该在一个SCC中,但是y不一定是SCC的根,怎么办呢?Lx=min(Lx,Ty)即可。

有同学会对3产生疑问:为什么不是Lx=min(Lx,Ly)呢?答案是,这是为了更好地定义,你一定要这么写也可以A题。

由于遍历到x的时候y的子树不一定已遍历完,Ly还没有更新完毕,所以Lx也不能算是节点及其子树能够间接访问到的在栈中的DFS序最小的点的DFS序,于是L的定义就会变得异常奇怪……那样Tarjan就写不粗论文了!!

反正不管怎么样,必定有Lx<=Tx,x必定不是SCC的根,对于y也同样木有影响,所以就这么决定了。

处理完x及其子树后,如果Lx=Tx,则不断弹栈直到弹出x为止,这一段都在且仅在以x为根的SCC中。

 

#include <stdio.h>
#define maxn 10000
#define maxm 50000
#define ADDEDGE(i,j) stp->next=map[i],(map[i]=stp++)->y=j
struct edge{struct edge*next;int y}*map[maxn],st[maxm],*stp=st;
int n,m,id,t[maxn],l[maxn],s[maxn],k;_Bool in[maxn];
inline getint(){
	int re=0,ch=getchar();_Bool k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}void dfs(i){
	struct edge*p=map[i];in[i]=1;
	for(t[s[k++]=i]=l[i]=++id;p;p=p->next)if(!t[p->y]){
		dfs(p->y);
		if(l[i]>l[p->y])l[i]=l[p->y];
	}else if(in[p->y]&&l[i]>t[p->y])l[i]=t[p->y];
	if(l[i]==t[i]){do{in[s[--k]]=0;printf("%d ",s[k]);}while(s[k]!=i);putchar('\n');}
}main(){
	int i;
	n=getint();m=getint();
	while(m--){
		i=getint()-1;
		ADDEDGE(i,getint()-1);
	}for(i=-1;++i!=n;)if(!t[i])dfs(i);
	return 0;
}
By Seter
  • 无匹配
Alyssa 说:
2022年12月21日 00:49

Tarjan's algorithm is a graph theoretical algorithm for finding the strongly connected components of a directed graph. It is named for its discoverer, Robert Tarjan, and is also known as the Tarjan–Kosaraju algorithm and the Kruskal–Tarjan algorithm. The algorithm has a wide range realtor homes for sale Moraga of applications in computer science, including input/output analysis, round-robin scheduling, data compression, and solving questions in graph theory.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee