模板题：B3609 [图论与代数结构 701] 强连通分量
题目描述
给定一张 n 个点 m 条边的有向图，求出其所有的强连通分量。
注意，本题可能存在重边和自环。
输入格式
第一行两个正整数 n ， m ，表示图的点数和边数。
接下来 m 行，每行两个正整数 u 和 v 表示一条边。
输出格式
第一行一个整数表示这张图的强连通分量数目。
接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。
本题让我们求出强连通分量的数量以及各强连通分量所包含的点。
解决这个问题需要用到taryan算法，下面简要介绍一下该算法的实现。
定义如下概念：
dfn[x]
可以这么理解，对一张图上所有没有遍历过的点进行dfs遍历，dfn[x]就是x点被遍历到的次序。又称dfs序。
low[x]
x所能到达的点中最小的dfs序
在一个强连通分量中，每两个点都是可以互相到达的，那么如果对于点x，low[x]!=dfn[x]，说明x可以访问到比它早遍历的点。
若dfn[x]=low[x]，说明点x能到达的dfs序最小的点就是x，找到了一个新的强连通分量。
使用栈存储遍历途中经过的点。
代码
#include<bits/stdc++.h>
using namespace std;
const int h=10001;
int head[h],last[h*10],to[h*10],tot=0;
void add_edge(int x,int y){
tot++;
last[tot]=head[x];
head[x]=tot;
to[tot]=y;
} int cnt=0;//标记强连通分量的数量
int timedrop=0;//标记每个点被访问的“时间”
int dfn[h];//dfn存的是这一点被访问的时间
int low[h];//low存的是 这个点可以到达的 “访问时间”最早的点
int belong[h];//存储某个点所属的强连通分量的编号
vector<int>scc[h];
stack<int>s;
bool instack[h];//标记这个点在不在栈内
bool printed[h];//存储该强连通分量是否被输出过
void dfs(int x){
//这是整个程序的核心部分，即如何求强连通分量 timedrop++;
dfn[x]=timedrop;//标记这个点被访问到的时间
low[x]=timedrop;//当前这个点能到达的“访问时间”最早的点只有它自己，以后可能会更新
s.push(x);//将这一点压入栈中
instack[x]=1;
for(int i=head[x];i!=0;i=last[i]){
//这里开始遍历该点可以到达的点，更新这一点的low
int y=to[i];
if(!dfn[y]){//这一点还没有被访问
dfs(y);//那么我们先得到这一点的dfn与low
low[x]=min(low[x],low[y]);//然后用这一点更新当前点
}
else
if(instack[y])//如果这一点在栈中，那这肯定是一个在x之前被访问的点
low[x]=min(low[y],low[x]);
//如果dfn[y]>0且它不在栈中呢？
//那么y已经找到了自己的强连通分量，和x没有关系了
}
if(dfn[x]==low[x]){
//这说明x不能到达在它之前被访问的点
//那么x就是它所在的强连通分量中第一个被访问的点
//并且在这个强连通分量中的所有点已经被压入栈中
//把这些点“取出”即可
cnt++;//新强连通分量内所有的点已经找出
while(s.top()!=x){
int q=s.top();
belong[q]=cnt;
instack[q]=0;
scc[cnt].push_back(q);
s.pop();
}
belong[x]=cnt;
instack[x]=0;
scc[cnt].push_back(x);
s.pop();
} }
int n,m;
int main(){
scanf("%d%d",&n,&m);
//建图
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
add_edge(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
dfs(i);
printf("%d\n",cnt);
//使用sort对每个强连通分量内的点进行升序排列（以前我也不知道）
for(int i=1;i<=cnt;++i)
sort(scc[i].begin(),scc[i].end());
for(int i=1;i<=n;i++){
int y=belong[i];
if(!printed[y]){
for(int j=0;j<scc[y].size();j++)
printf("%d ",scc[y][j]);
printf("\n");
printed[y]=1;
}
else
continue;
}
return 0;
}
