#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
void read(T& x){x=0;char ch=getchar();long long f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}
template<typename T,typename... Args>
void read(T& first,Args&... args){read(first);read(args...);}
template<typename T>
void write(T arg){T x=arg;if (x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');}
template<typename T,typename... Args>
void write(T arg,Args... args){write(arg);if(sizeof...(args) !=0){putchar(' ');write(args...);}}
const int N=1e4+5,M=1e5+5;
int dfn[N],low[N],head[N];
int Cnt;
struct edge{
int to, nxt;
}e[M<<1];
void add(int f, int t)
{
e[++Cnt].to = t;
e[Cnt].nxt = head[f];
head[f] = Cnt;
}
int n,m,id,cnt;
bool S[N];
int v[N];
stack<int> s;
vector<int> ans[N];
void dfs(int root){//tarjan
low[root]=++id,dfn[root]=low[root];
s.push(root);
S[root]=1;
for(int i=head[root];~i;i=e[i].nxt){
int u=e[i].to;
if(!dfn[u]){
dfs(u);
low[root]=min(low[root],low[u]);
}
else if(S[u]){
low[root]=min(low[root],low[u]);
}
}
if(dfn[root]==low[root]){
cnt++;
ans[cnt].push_back(root);
while(!s.empty()&&s.top()!=root){
v[s.top()]=cnt;
S[s.top()]=0;
ans[cnt].push_back(s.top());
s.pop();
}
S[root]=0;
v[root]=cnt;
if(!s.empty())s.pop();
}
}
bool flags[N];
int main()
{
memset(head,-1,sizeof head);
read(n,m);
for(int i=1;i<=m;i++){
int x,y;
read(x,y);
add(x,y);
}
for(int i=1;i<=n;i++){
if(!dfn[n])dfs(n);
}
write(cnt);
putchar('\n');
for(int i=1;i<=cnt;i++){
sort(ans[i].begin(),ans[i].end());
}
for(int i=1;i<=n;i++){
if(flags[v[i]])continue;
flags[v[i]]=1;
for(int j=0;j<=ans[v[i]].size()-1;j++){
write(ans[v[i]][j]);
putchar(' ');
}
putchar('\n');
}
return 0;
}
题目:B3609