Pagini recente » Cod sursa (job #3131788) | Cod sursa (job #1758884) | Cod sursa (job #2948586) | Cod sursa (job #1439400) | Cod sursa (job #325884)
Cod sursa(job #325884)
#include <stdio.h>
#include <stdlib.h>
#define N 100005
int *v[N],*t[N],n,m,f[N],ft[N],s1[N],s2[N],c;
void dfs(int x){
f[x]=1;
for(int i=1;i<=v[x][0];i++)
if(!f[v[x][i]])
dfs(v[x][i]);
s1[++s1[0]]=x;
}
void dfs2(int x){
ft[x]=1;
for(int i=1;i<=t[x][0];i++)
if(!ft[t[x][i]])
dfs2(t[x][i]);
s2[++s2[0]]=x;
}
void solve(){
int i;
for(i=1;i<=n;i++)
if(!f[i])
dfs(i);
for(i=n;i;i--)
if(!ft[s1[i]]){
c++;
dfs2(s1[i]);
s2[0]++;
}
printf("%d\n",c);
for(i=1;i<=s2[0];i++)
if(s2[i])
printf("%d ",s2[i]);
else printf("\n");
}
int main(){
int i,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
//scanf("%d%d",&x,&y);
v[i]=(int*)malloc(4);
t[i]=(int*)malloc(4);
v[i][0]=t[i][0]=0;
}
for(i=1;i<=m;i++){
scanf("%d%d",&x,&y);
v[x][0]++;
v[x]=(int*)realloc(v[x], (v[x][0]+1)*4); v[x][v[x][0]]=y;
t[y][0]++;
t[y]=(int*)realloc(t[y], (t[y][0]+1)*4); t[y][t[y][0]]=x;
}
solve();
return 0;
}