tarjan2

本文主要是介绍tarjan2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

反过来调过去，我还是感觉没学明白缩点

• 讲一个有向图中的所有强连通分量缩成一个点后，构成的新图是一个DAG。
• 一个点所在的强连通分量一定被该点所在DFS搜索树所包含
• 树上的边大致分为：树枝边，前向边（从上往下指），后向边（从下往上指），横叉变。其中前向边肉眼可见地没什么卵用

接下来开始算法流程。

• tarjan的精髓如上次所说，在于DFS搜索树，在DFS搜索树中强连通分量以怎样形式存在是关键问题。对于x，存在祖宗y，从x出发可经过横叉边，返祖边，后向边到达y，则x，y属于同一强连通分量。操作中记录最小 y 为：low(x)=dfn(y)。（其中单点也算强连通块）如果有一个dfn_x=low_x ，那么就是说 x 在一个新的强连通块里，同理，low_x的初始也就是dfn_x。
• 我们用一个栈来维护 已经被遍历过的、还未确定隶属哪个强连通分量的 点，在该栈中越靠栈顶DFS序越靠后（是栈底元素的后代）。
• 关于low_x的求法、更新。考虑如何求low_x：low_x 可能被更新，当且仅当x连出了一条树枝边，横叉边或后向边。设该边连向点 v

1.  树枝边： low_x= min(low_x,low_v) v 到达的点x一定可以到达，且v与x有祖宗关系
2.  后向边： low_x= min(low_x,low_v) v 的祖先一定是 x 的祖先
3.  横叉边：此时分两种情况考虑的
            当 v 点已经退栈时，那么点v可到达的DFS序最小的祖先不是x的祖先，对 low_x 没有贡献； 当点v还在栈中时，v 点可到达的DFS序最小的祖先是x的祖先，有 low_x=min(low_x,low_v) (点v可到达的DFS序最小的祖先一定是x的，v 点能到达的点，x一定能到达)  特别地,由于前向边的更新对于求强连分量没有帮(更新是重复的)，所以我们也可以有 low_x=min(low_x,low_v)

         那么我们只需判断点 x 连出的边是哪一条就可以转移了。显然,当 dfn_v=0 时（此时v未被访问过），这是一条树枝边。我们再维护一个 col 数组， col_i 表示点 i 所在的强连通分量,在点 i 退栈时,我们对col进行赋值,那么当 dfn_v≠0&&col_v=0 时,点v一定在栈中（后向边指向的点一定在栈中,横叉边指向的点满足此条件时在栈中,而前向边是否存在与答案无关），此时用 low_x=min(low_x,low_v) 转移即可,否则无需转移。该算法时间复杂度为(n+m),因为深度优先遍历每个点只会经过一次,每条边也只会访问一次,而每个点都只会进/出栈一次,所以总时间复杂度为(n+m)

//把一个点当成根提溜出来，抖搂抖搂成一棵树 
void dfs(int u)
{
//记录dfs序
//可通过任意多dfs边与最多一条非树返祖边到达的、本强连通分量内最小点 
	dfn[u]=low[u]=++dfs_clock;
	s.push(u);
	for(int v:g[u])
	{
		if(!dfn[v])//树边 
		{
			dfs(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccnum[v])//返祖 
			low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		scccnt++;//强连通块+1 
		while(1)
		{
			int x=s.top();
			s.pop();
			sccnum[x]=scccnt;
			sccsz[scccnt]++;
			if(x==u) break;
		}
	}
}

这篇关于tarjan2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！