Pagini recente » Cod sursa (job #112181) | Cod sursa (job #931572) | Cod sursa (job #626820) | Cod sursa (job #2870535) | Cod sursa (job #1714219)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define N 100100
#define vec muc[k][i]
using namespace std;
vector<int> muc[N];
int grad[N],stk[N],viz[N],viz_stk[N];
int sp;
int low[N],prenum[N],ctc[3*N],ifin,nrctc;
int pop(){
viz_stk[ stk[sp-1] ]=0;
return stk[--sp];
}
void push(int x){
viz_stk[ x ] = 1;
stk[sp++]=x;
}
int cnt;
void dfs(int k){
int i;
push(k);
viz[k]=1;
prenum[k]=low[k]=++cnt;
for(i=0;i<grad[k];i++){
if( viz[vec]==0 ){
dfs(vec);
low[k]=min(low[k],low[vec] );
}else{
if(viz_stk[ vec ]==1){
low[k]=min(low[k],prenum[vec]);
}
}
}
if(prenum[k]==low[k]){
nrctc++;
do{
i=pop();
ctc[ifin++]=i;
}while(k!=i);
ctc[ifin++]=-1;
}
}
int main(){
int i,n,m;
int x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
muc[x].push_back(y);
grad[x]++;
}
for(i=1;i<=n;i++){
if(viz[i]==0){
dfs(i);
}
}
printf("%d\n",nrctc);
for(i=0;i<ifin;i++){
if(ctc[i]==-1){
printf("\n");
continue;
}
printf("%d ",ctc[i]);
}
return 0;
}