Pagini recente » Cod sursa (job #1724823) | Cod sursa (job #51961) | Cod sursa (job #583102) | Cod sursa (job #2838901) | Cod sursa (job #1006281)
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#define pb push_back
using namespace std;
vector<int> g[102020],stack,viz,low,iss;
vector<int> aux;
vector<vector <int> > comp;
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 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]){
aux.clear();
do{
aux.pb(stack[k]);
iss[stack[k]] = 0;
--k;
}while(stack[k+1] != x);
comp.pb(aux);
}
}
void init(){
stack.resize(N+10);
viz.resize(N+10);
iss.resize(N+10);
low.resize(N+10);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&N,&M);
init();
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;
}