Pagini recente » Cod sursa (job #2173417) | Cod sursa (job #1102206) | Cod sursa (job #234444) | Cod sursa (job #1999895) | Cod sursa (job #1006280)
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#define pb push_back
using namespace std;
vector<int> g[102020],stack;
vector<int> aux;
vector<vector <int> > comp;
int viz[101010];
int low[101010];
int iss[101010];
int k,index=1;
int N,M,x,y;
void printv(vector<int> v){
for(int i=0;i<v.size();++i){
printf("%d ",v[i]);
}
printf("\n");
}
void show_stack(){
for(int i=1;i<=k;++i){
printf("%d %d\n",stack[i],low[stack[i]]);
}
}
void df(int x){
viz[x] = index;
low[x] = index;
stack[++k] = x;
iss[x] = 1;
++index;
for(int i=0;i<g[x].size();++i){
if(viz[g[x][i]] == 0){
df(g[x][i]);
low[x] = min(low[x],low[g[x][i]]);
}
else{
if(iss[g[x][i]]){
low[x] = min(low[x],low[g[x][i]]);
}
}
}
if(low[x] == viz[x]){
//printf("%d %d %d\n",x,low[x],stack[k]);
aux.clear();
do{
aux.pb(stack[k]);
iss[stack[k]] = 0;
--k;
}while(stack[k+1] != x);
//show_stack();
comp.pb(aux);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
stack.resize(N+10);
for(int i=1;i<=M;++i){
scanf("%d%d",&x,&y);
g[x].pb(y);
}
for(int i=1;i<=N;++i){
if(viz[i]==0){
df(i);
}
}
printf("%d\n",comp.size());
for(int i=0;i<comp.size();++i){
printv(comp[i]);
}
return 0;
}