psh18582512217 @ 2024-08-24 12:39:04
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll scc,inst[1000005],ti,n,m,head[1000005],cnt,dfn[1000005],low[1000005];
struct Edge{
ll next,to;
}e[1000005];
vector<ll> ans[1000005];
void add(ll next,ll to){
e[++cnt].to=to;
e[cnt].next=head[next];
head[next]=cnt;
}
stack<ll> s;
void tarjan(ll x){
dfn[x]=low[x]=++ti;
s.push(x);
inst[x]=1;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(inst[x]){
low[x]=min(low[x],low[y]);
}
}
if(dfn[x]==low[x]){
int y;
scc++;
do{
y=s.top();
ans[scc].push_back(y);
s.pop();
}while(x!=y);
}
}
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);
}
}
cout<<scc<<endl;
for(int i=1;i<=scc;i++){
sort(ans[i].begin(),ans[i].end());
}
sort(ans+1,ans+scc+1);
for(int i=1;i<=scc;i++){
for(ll &j : ans[i]){
cout<<j<<" ";
}
cout<<endl;
}
return 0;
}
by sakura_21 @ 2024-09-02 15:03:15
@psh18582512217 你pop那里没有清空标记,我也一样,笑死