Tarjan求强连通分量

dfn DFS序

low 向前可以到达的dfn最小的点

#include<bits/stdc++.h>
using namespace std;
vector<int>G[50001];
int n,m,tot,at;
bool vis[50001],V[50001];
int dfn[50001];
int low[50001];
vector<int>ans[50001];
stack<int>s;
void tarjan(int u){
	s.push(u);
	vis[u]=true;
	dfn[u]=++tot;
	low[u]=dfn[u];
	for(auto v:G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u]){
		at++;
		int tmp;
		do{
			tmp=s.top();
			ans[at].push_back(tmp);
			vis[tmp]=false;
			s.pop();
		}while(!s.empty()&&tmp!=u);
	}
}
int main(){
#ifdef USE_FILE_IO
	freopen("code.in","r",stdin);
	freopen("code.out","w",stdout);
#endif
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int op,u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		tot=0;
		if(!dfn[i])tarjan(i);
	}
	cout<<at<<endl;
	for(int i=1;i<=at;i++){
		sort(ans[i].begin(),ans[i].end());
	}
	sort(ans+1,ans+at+1);
	for(int i=1;i<=at;i++){
		for(auto j:ans[i]){
			cout<<j<<" ";
		}
		cout<<endl;
	}
	return 0;
}