秀……虚空 @ 2023-09-06 16:15:06
求调
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int vis[maxn];
int dfn[maxn],low[maxn],num,n,m;
int ver[maxn],Next[maxn],head[maxn],tot,top,_stack[maxn],ins[maxn],cnt,c[maxn];
vector<int> scc[maxn];
void add(int x,int y){
ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
dfn[x]=low[x]=++num;
_stack[++top]=x,ins[x]=1;
for(int i=head[x];i;i=Next[i]){
if(!dfn[ver[i]]){
tarjan(ver[i]);
low[x]=min(low[x],low[ver[i]]);
}
else if(ins[ver[i]]){
low[x]=min(low[x],dfn[ver[i]]);
}
}
if(dfn[x]==low[x]){
cnt++;int y;
do{
y=_stack[top--],ins[y]=0;
c[y]=cnt,scc[cnt].push_back(y);
}while(x!=y);
}
}
int vc[maxn],nc[maxn],hc[maxn],tc;
void add_c(int x,int y){
vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
add(x,y);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=cnt;i++){
sort(scc[i].begin(),scc[i].end());
}
memset(vis,0,sizeof(vis));
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(vis[c[i]])continue;
vis[c[i]]=1;
for(int j=0;j<scc[c[i]].size();j++){
cout<<scc[c[i]][j]<<' ';
}
cout<<endl;
}
/*
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(c[x]==c[y])continue;
add_c(c[x],c[y]);
}
}*/
return 0;
}