用Tarjan帮村里通网指北——求强连通分量篇

2024-02-28 12:05:04

最近一直在学\(Tarjan\)，那么我们来从菜逼（我）的角度来看一下\(Tarjan\)从0到1的学习心得吧。

\(Tarjan\)算法是\(Robert\) \(Tarjan\)(罗伯特·塔扬)大神发明的求有向图中强连通分量的算法。

更厉害的是，\(Tarjan\)算法的主要思想是以dfs为基础实现图上的搜索。所以在各种改进与变化后有了更广泛的作用，比如说“求割点”。

  • 强连通分量

pre芝士：

如果两个顶点可以相互通达，则称两个顶点强连通(\(strongly\) \(connected\))。

如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(\(strongly\) \(connected\) \(components\))。

—————— From 百度百科

\(Tarjan\) 算法的基础思想其实非常简单，在对当前这个有向图进行DFS时，我们走的每一步最后必定形成一颗搜索树，那么我们可以简单证明每颗搜索树便是图中的一个强连通分量。因为在搜索时，你在遍历到最深的节点后开始回溯，从去到回，而显然便可以保证这颗子树的每一个点可以相互到达，则必然成为一个强连通分量。

如果还是不明白，那我们可以抛开\(Tarjan\)算法来想想对于求强连通分量我们应该怎么暴力。我们可以选择当前图中一个起点\(U\)，再取一个\(V\)作为一个终点，然后分别DFS，双向遍历，最后在路径的点集中取二者交集则为强连通分量。这个很明显是\(O( N^{2}+M)\)的复杂度，对于大部分图论题目是超时的。

那么可以请出伟大的\(Tarjan\)算法了。

\(Tarjan\)是基于DFS的算法，更进一步说，\(Tarjan\)的答案求解建立于DFS时每个点所遍历到的顺序（也就是在搜索树中的位置）。于是乎我们先引出数组dfn[],所代表的是每个点被遍历到的时间，也就是时间戳数组。dfn在每个点被遍历到就被定下来的，不会改变。

所以dfn[u]=++tot//tot是已经遍历了点的个数

那么我们怎么得出强连通分量的呢，我们上面提出子树的相关概念。那么对于一棵树，我们自然会有一个根节点，其实对于子树我们是没有根的，但是对于\(Tarjan\)算法，我们定义每个强连通分量都有其根，其实就是这个强连通分量的代表元，（这一点在进一步的缩点算法中体现了出来）我们进一步发现，DFS在访问时，访问完当前子树的所有子节点并回溯时，就会最终回到这个强连通分量子树的那个根。

但是这样还不够，我们怎么把子节点也加入强连通分量这个子集并且灵活处理它们呢?

于是我们再加入2个工具Stack和low数组。

  • \(Stack\) 栈

我们在DFS的时候将所有节点加入栈中，在回溯时判断当前节点是否为一棵子树的根节点。如果是，那么删除它并开始记录这个强连通分量，而在它之前出堆栈且还不属于其他强连通分量的节点构成了该节点所在的强连通分量。

  • 回溯最小值\(index-low\)数组

low数组在回溯到当前节点进行更新，表示从某个点出发经有向边可到达的所有节点中最小的回溯值。也就是某点或其子树能够追溯到的最早的栈中节点的次序号。（这个“栈中”非常重要，不在栈中显然不能提供节点信息，不然会导致不同强连通分量反而连起来，所以我们要开数组记录一个点当前是否在栈中，在才能用来更新。）

显然一个点的low肯定小于等于其dfn。当一个点遍历从该点可到的所有其他点中再也没有low值更小的时候，那么这个强连通分量（这个子树）在搜索树中的使命就完成了。虽然low是要更新找最小值的，但是最大也就是自身的dfn于是初始值也是

low[x]=++tot

对于low的更新

for(int i=head[x];i;i=e[i].nxt)
	{
		int go=e[i].to;
		if(!dfn[go])
                //对于Tarjan算法每个点只需要遍历一遍，
                //如果遍历过了，根据dfs一路到底的性质
                //那么该点一定已经算入其应该在的强连通分量中
                //不需要再次遍历
		{
			Tarjan(go);//深入
			low[x]=mn(low[x],low[go]);
                        //用low[go]更新low[x]是因为
                        //go是可以x可以到达的点，
                        //并且还未算入任何强连通分量中
		}
		else
		{
			if(in[go])low[x]=mn(low[x],dfn[go]);
                        //如果go在栈中，
                        //仍符合“待加入”的情况，
                        //所以dfn[go]可以用来更新
/*（在求强连通分量时low[go]也可以使用,
但是割点则不行，这个我们在后续的割点笔记中会谈到）*/
		}
	}

于是在完成某点的遍历后，我们判断dfn[u]是否等于low[u]，如果是，则开始统计该强连通分量的信息。

if(dfn[x]==low[x])
	{
		secs++;
           //强连通分量的个数，
           //由于每个强连通分量不会减回去更新，
           //所以这个也可以代表当前强连通分量的编号。
		int tp=s.top();
		do
		{
			tp=s.top();s.pop();//删除栈顶元素
			sec[tp]=secs;//并统计为该强连通分量的点
			siz[secs]++;//记录该强连通分量大小，部分题目有用
			in[tp]=0;//记录已经不在栈中，这个对于更新low值有用
		}while(x!=tp);//直到找到根弹出便统计完一个强联通分量
	}

我们对这段代码进行一个思考，每次Tarjan(x)时会把x点先压入栈中，然后在遍历出边到达的那些点时，会继续dfs到其他点继续压入该点x上，回溯后我们终于发现x是一个子树的根便开始找。弹出栈中所谓“在它之前出堆栈且还不属于其他强连通分量的节点”。

我们现在来稍微模拟一下：

用Tarjan帮村里通网指北——求强连通分量篇

我们从\(Node\) \(1\)开始DFS，一直走到点6才开始第一次回溯。

用Tarjan帮村里通网指北——求强连通分量篇

回溯到点\(3\)for循环走到第二条边，往\(4\)进发,回溯过程中，low[go]一直大于low[x],所以没发生更新。

用Tarjan帮村里通网指北——求强连通分量篇

从\(4\)到\(1\)和\(6\)回溯回来可以更新low[4]，然后回溯去3又更新了low[3]，这两个点都向\(1\)的点集靠拢，成为强连通分量的成员了。

用Tarjan帮村里通网指北——求强连通分量篇

到点2的时候通过dfn[4]对\(2\)进行了更新，压入栈中。

用Tarjan帮村里通网指北——求强连通分量篇

最后统计出如下强连通分量。

在第一遍dfs回到\(6，5\)时他们没发生更新，也就压入便弹出了，所以单独成强连通分量，但是到4时一直更新low值，压入没再弹出。，直到回到\(1\)这个根才开始统计这个有4个元素的分量，从栈中弹出，程序也结束了。

\(\textit{——Graph Editor from CS Academy}\)

整体代码

void Tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	s.push(x);in[x]=1;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int go=e[i].to;
		if(dfn[go]==0)
		{
			Tarjan(go);
			low[x]=mn(low[x],low[go]);
		}
		else
		{
			if(in[go])low[x]=mn(low[x],dfn[go]);
		}
	}
	if(dfn[x]==low[x])
	{
		secs++;
		int tp=s.top();
		do
		{
			tp=s.top();s.pop();
			sec[tp]=secs;
			siz[secs]++;
			in[tp]=0;
		}while(x!=tp);
	}
}

  • 缩点

缩点的内容，其实非常简单。

如果会了强连通分量，那么我们只需要知道将每个强连通分量都缩成一个单独的点并且重新建图就行。因为我们在\(Tarjan\)时存下了强连通分量的信息（各自的编号与大小与权值相关），所以可以很快解决，具体看代码。

for(int i=1;i<=m;i++)
{
	if(sec[x[i]]!=sec[y[i]])add(sec[x[i]],sec[y[i]]);
   	//x[i],y[i]是之前记下的每一条边的出入点。
        //如果a->b但是a和b不在强连通分量内，
        //那么这两个点所属的强连通分量则相连，
        //就在缩完的点之间建单向边
}

缩点操作的意义就在于，在考察缩点的题目中一般保证强连通分量之间形成的关系相通，那么缩点后可以更直观更有效率的解决相关问题。

其余分析

我们根据性质可得，每个点在\(Tarjan\)算法中只会被遍历一次，所以时间是线性的，相当于每条边每个点不重复的走一遍，复杂度便是\(O(|V|+|E|)\)。

																强连通分量部分——2020.10.12 写在机房

Reference：

上一篇：强联通分量tarjan


下一篇：JOISC 2020 Day4T1 首都 (Capital City) 题解