Pagini recente » Cod sursa (job #2875506) | Cod sursa (job #1720047) | Cod sursa (job #1074241) | Cod sursa (job #3171722) | Cod sursa (job #1713198)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 110000
#define M 210000
#define vec lis[i].val
#define revvec revlis[i].val
using namespace std;
int head[N],revhead[N],postnum[N],ord[2*N];
bool viz[N];
int ifin,revifin;
int n;
struct muc{
int val,next;
};
struct muc lis[M],revlis[M];
void Add_arc(int x,int y);
void revAdd_arc(int x,int y);
int cnt;
void bfs(int k){
int i;
viz[k]=1;
for(i=head[k] ;i!=-1;i=lis[i].next){
if(viz[vec]==0){
bfs(vec);
}
}
postnum[cnt++]=k;
}
int nrnod;
void revdfs(int k) {
int i;
viz[k]=1;
for (i = revhead[k]; i!=-1 ; i=revlis[i].next){
if (viz[revvec] == 0){
revdfs(revvec);
}
}
ord[nrnod++]=k;
}
void Init(){
memset(head,-1,(n+1)*sizeof(int) );
memset(revhead,-1,(n+1)*sizeof(int) );
ifin=revifin=cnt=0;
}
int main(){
int m,i,x,y;
int nrctc=0;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
Init();
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
Add_arc(x,y);
revAdd_arc(y,x);
}
for(i=1;i<=n;i++){
if(viz[i]==0){
bfs(i);
}
}
memset(viz,0,(n+1)*sizeof(int));
for(i=cnt-1;i>=0;i--){
if(viz[ postnum[i] ]==0){
revdfs(postnum[i]);
ord[nrnod++]=-1;
nrctc++;
}
}
printf("%d\n",nrctc);
for(i=0;i<nrnod;i++){
if(ord[i]==-1){
printf("\n");
continue;
}
printf("%d ",ord[i]);
}
return 0;
}
void Add_arc(int x,int y){
lis[ifin].val=y;
lis[ifin].next=head[x];
head[x]=ifin;
ifin++;
}
void revAdd_arc(int x,int y){
revlis[revifin].val=y;
revlis[revifin].next=revhead[x];
revhead[x]=revifin;
revifin++;
}