自动搬运

查看原文

来自洛谷，原作者为

	Daidly 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 21:13:52，当前版本为作者最后更新于2021-07-20 19:21:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

定义

• cnt：当前有几个强连通分量。

• belong[MAXN]：$i$ 个点属于第几个强连通分量。

• s[MAXN]：手写栈。

• len：栈里面有几个点。

• dfn[MAXN]：$i$ 点是第几个被 dfs 到的。

• low[MAXN]：从 $i$ 出发可以走任意边，但走的最后一条边必须是回边的情况下，能够达到的所有点中 dfn 值最小的是多少。

• tot：当前 dfs 点数。

• instack[MAXN]：第 $i$ 个点在不在栈里面。

回边：从某个结点指向其某个祖先的边叫做回边。

横叉边：从某个结点指向树中的另一子树中的某结点的边。

一个环必定是由一个树连一些边变成的。

树边：在这棵树上的边。

非树边：即为回边或横插边。

考虑在图中的一个树上结合其他非树边构成一个强连通分量。

算法 Tarjan

结合代码讲解，建议看一步讲解，一步代码：

前部分代码：

void dfs(int x){
	dfn[x]=low[x]=++tot;
	s[++len]=x;
	instack[x]=1;
    for(int i=head[x];i;i=e[i].next){
    	int y=e[i].to;
    	if(!dfn[y]){
    		dfs(y);
    		low[x]=min(low[x],low[y]);
		}else{
		    if(instack[y])low[x]=min(low[x],low[y]);
		}
	}
	...... 
	......
	...... 
}

从 $1$ 开始 dfs，把遍历到的节点加入栈中。

初始化：$1$ 是第一个 dfs 到的，从 $1$ 出发可以走任意边，能够达到的所有点中 dfn 值最小的是 $1$，$1$ 入栈，标记为栈中。

遍历 $1$ 的所有连边，找到连点，如果连点。

• 若 $y$ 还没有被遍历过，遍历连点，然后更新 low 值。

• 若 $y$ 已被遍历过，并且在栈中，由于 $x$ 也在栈中，并且根据 low 的特殊定义，那么可以通过回边回到 $x$，所以 $y$ 可以用来更新 $x$。

• 若 $y$ 已被遍历过，并且不在栈中，说明更新完毕，不能用来更新当前点，跳过。

由于 $y$ 是 $x$ 的连点，所有 $y$ 能走到的 $x$ 也能走到，用 $y$ 的 low 更新 $x$ 的 low。

进栈和更新处理过了，开始处理出栈。

• 发现一个性质：如果点 $i$ 的 dfn 值和 low 值一样，那么说明从 $i$ 出发可以走任意边，但走的最后一条边必须是回边的情况下，能够达到的所有点中 dfn 值最小就是他自己。

• 换句话说，点 $i$ 是这个强连通分量最上面的点，因为无法达到 dfn 值比它自己更小的点了。

• 该结点在遍历的过程中，为这个强连通分量中第一个被访问的结点，因为它的 dfn 值和 low 值比其他的点都小，不会被该连通分量中的其他结点所影响。

后部分代码：

void dfs(int x){
	......
	......
	......
	if(dfn[x]==low[x]){
	    cnt++;
	    ans[cnt].push_back(x);
	    while(s[len]!=x){
	    	belong[s[len]]=cnt;
	    	instack[s[len]]=0;
	    	ans[cnt].push_back(s[len]);
	    	len--;
		}
		len--;
		instack[x]=0;
		belong[x]=cnt;
	} 
}

若 $dfn_i=low_i$：

将强连通分量数加一，因为有一个强连通分量的“头头”来了，然后记录这个连通块。

Q：为什么遍历到这一个强连通分量的“头头”，也就是第一个点，就要出栈之类的，不应该继续往下遍历吗？

A：那你就理解错了，部分的操作进行是从下往上的，发现前部分代码有一个 dfs(y)，就说明这一过程是从下往上回溯的，其实 $x$ 早已在栈中了。

• 不明白的同学可以看看前面的代码。

进行记录操作即可。

关于本题

对于每一个点，若没有遍历过，则跑一遍 dfs。

题目还要求要排序输出，可以用一个动态数组存答案排序输出。

代码

为了大家更好地理解各个变量，我将变量定义在代码中列成了一列。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
const int MAXM=100005;
struct node{
	int to,next;
}e[MAXM<<1];
int head[MAXN],num;
bool instack[MAXN];
int s[MAXN],len;
int low[MAXN];
int cnt;
int belong[MAXN];
int n,m;
int f[MAXN];
vector<int>ans[MAXN];
void add(int u,int v){
    e[++num].to=v;
    e[num].next=head[u];
    head[u]=num;
}
int dfn[MAXN],tot;
void dfs(int x){
	dfn[x]=low[x]=++tot;
	s[++len]=x;
	instack[x]=1;
    for(int i=head[x];i;i=e[i].next){
    	int y=e[i].to;
    	if(!dfn[y]){
    		dfs(y);
    		low[x]=min(low[x],low[y]);
		}else{
		    if(instack[y])low[x]=min(low[x],low[y]);
		}
	}
	if(dfn[x]==low[x]){
	    cnt++;
	    ans[cnt].push_back(x);
	    while(s[len]!=x){
	    	belong[s[len]]=cnt;
	    	instack[s[len]]=0;
	    	ans[cnt].push_back(s[len]);
	    	len--;
		}
		len--;
		instack[x]=0;
		belong[x]=cnt;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i])dfs(i);
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;++i){
		sort(ans[i].begin(),ans[i].end());
	}
	for(int i=1;i<=n;++i){
		if(f[belong[i]])continue;
		f[belong[i]]=1;
		for(int j=0;j<ans[belong[i]].size();++j){
			cout<<ans[belong[i]][j]<<" ";
		}cout<<endl;
	}
	return 0;
}

如果你觉得这篇题解讲得还算好的话，可以点个赞支持一下呀，谢谢大家！