强连通分量

我们首先定义两种边：返祖边为从一个点指向其祖先的边；横叉边从某个点指向树中另一个子树中的点的边。两者统称为非树边。而剩下的边即为树边，树边也就是在 \(dfs\) 树上的边。

我们定义 \(dfn_i\) 为 \(i\) 是第几个被 \(dfs\) 到的，\(low_i\) 从 \(i\) 出发走任意条边，但是最后一条边必须是返祖边的情况下能够到达的点的 \(dfn\) 的最小值。

于是我们便有了求出 \(dfn\) 和 \(low\) 的代码：

void tar(int u){
	low[u]=dfn[u]=++tot;
	stk[++top]=u;
	ist[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tar(j);
			low[u]=min(low[u],low[j]);
		}
		else if(ist[j]){
			low[u]=min(low[u],dfn[j]);
		}
	}
}

接着我们考虑怎么通过 \(low\) 和 \(dfn\) 求出强连通分量。

我们假设现在遇到了一个点 \(x\)，并且 \(dfn_x=low_x\)。这说明从 \(x\) 出发按照之前的要求能走到的 \(dfn\) 最小的点是他自己。

换句话说，\(x\) 是其所在强连通分量的最上面的点。

于是我们不断弹出栈，直到弹出了 \(x\)（不难证明 \(x\) 在栈中），弹出的这些点与 \(x\) 同属一个强连通分量，于是就做完了。

完整代码：

#include<bits/stdc++.h>
#define int long long
#define N 10005
#define M 100005
using namespace std;
int n,m,h[N],e[M],ne[M],idx,cnt,tot;
int stk[N],col[N],dfn[N],low[N],top;
bool ist[N],st[N];
vector<int>res[N];
void add(int a,int b){
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void tar(int u){
	low[u]=dfn[u]=++tot;
	stk[++top]=u;
	ist[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!dfn[j]){
			tar(j);
			low[u]=min(low[u],low[j]);
		}
		else if(ist[j]){
			low[u]=min(low[u],dfn[j]);
		}
	}
	if(dfn[u]==low[u]){
		cnt++;
		int y;
		do{
			y=stk[top--];
			ist[y]=0;
			col[y]=cnt;
			res[cnt].push_back(y);
		}while(y!=u);
	}
}
signed main(){
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tar(i);
		}
	}
	cout<<cnt<<'\n';
	for(int i=1;i<=n;i++){
		if(!st[col[i]]){
			sort(res[col[i]].begin(),res[col[i]].end());
			for(auto it:res[col[i]]){
				cout<<it<<' ';
			}
			cout<<'\n';
			st[col[i]]=1;
		}
	}
	return 0;
}