B3609 [图论与代数结构 701] 强连通分量 题解
定义
-
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]);
}
}
......
......
......
}从 dfs，把遍历到的节点加入栈中。
初始化：dfs 到的，从 dfn 值最小的是
遍历
-
若
y 还没有被遍历过，遍历连点，然后更新low值。 -
若
y 已被遍历过，并且在栈中，由于x 也在栈中，并且根据low的特殊定义，那么可以通过回边回到x ，所以y 可以用来更新x 。 -
若
y 已被遍历过，并且不在栈中，说明更新完毕，不能用来更新当前点，跳过。
由于 low 更新 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;
}
}若
将强连通分量数加一，因为有一个强连通分量的“头头”来了，然后记录这个连通块。
Q：为什么遍历到这一个强连通分量的“头头”，也就是第一个点，就要出栈之类的，不应该继续往下遍历吗？
A：那你就理解错了，部分的操作进行是从下往上的，发现前部分代码有一个 dfs(y)，就说明这一过程是从下往上回溯的，其实
- 不明白的同学可以看看前面的代码。
进行记录操作即可。
关于本题
对于每一个点，若没有遍历过，则跑一遍 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;
}如果你觉得这篇题解讲得还算好的话，可以点个赞支持一下呀，谢谢大家！