Pagini recente » Cod sursa (job #1165947) | Cod sursa (job #2045199) | Cod sursa (job #2406150) | Cod sursa (job #3041609) | Cod sursa (job #2443368)
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
#define maxn 100005
vector<int>ans[maxn],V[maxn],Stack;
int onstack[maxn],g[maxn],index[maxn],lowlink[maxn],Index=1,N,M,number,x;
void read(){
cin>>N>>M;
int x,y;
for(int i=1; i<=M; i++){
cin>>x>>y;
V[x].push_back(y);
g[x]++;
}
}
void tarjan(int nod){
index[nod]=Index;
lowlink[nod]=Index;
Index++;
Stack.push_back(nod);
onstack[nod]=1;
for(int i=g[nod]-1; i>=0; i--){
if(index[V[nod][i]]==0){
tarjan(V[nod][i]);
lowlink[nod]=min(lowlink[V[nod][i]],lowlink[nod]);
} else if(onstack[V[nod][i]])
lowlink[nod]=min(lowlink[nod],lowlink[V[nod][i]]);
}
if(lowlink[nod]==index[nod]){
number++;
do{
x=Stack.back();
ans[number].push_back(x);
onstack[x]=0;
Stack.pop_back();
}while(nod!=x);
}
}
void solve(){
for(int i=1; i<=N; i++)
if(index[i]==0)
tarjan(i);
cout<<number<<'\n';
for(int i=1; i<=number; i++){
while(!ans[i].empty()){
cout<<ans[i].back()<<' ';
ans[i].pop_back();
}
cout<<'\n';
}
}
int main(){
read();
solve();
}