#include<stdio.h>
int vertex,indegree1[110],strtop[110];
int graph[110][110];
void topo(int vertex);
int main()
{
int i,j,edge,p,x,y,kk,ff,rr,pp;
while(scanf("%d%d",&vertex,&edge)==2)
{
if((vertex==0)&&(edge==0))
break;
for(ff=1;ff<=vertex;ff++)
for(rr=1;rr<=vertex;rr++)
graph[ff][rr]=0;
for(i=1;i<=edge;i++)
{
scanf("%d%d",&x,&y);
graph[x][y]=1;
}
for(kk=1;kk<=vertex;kk++)
{ indegree1[kk]=0;
strtop[kk]=0;
}
for(i=1;i<=vertex;i++)
for(j=1;j<=vertex;j++)
if(graph[j][i]==1)
indegree1[i]++;
topo(vertex);
for(pp=1;pp<=vertex;pp++)
printf("%d ",strtop[pp]);
printf("\n");
}
return 0;
}
void topo(int vertex)
{
int l,p,xx,node,top=0,d=0;
for(l=1;l<=vertex;l++)
if(indegree1[l]==0)
strtop[++top]=l;
while(d!=vertex)
{
node=strtop[++d];
for(xx=1;xx<=vertex;xx++)
if(graph[node][xx]==1)
{
indegree1[xx]=indegree1[xx]-1;
if(indegree1[xx]==0)
strtop[++top]=xx;
}
}
}
int vertex,indegree1[110],strtop[110];
int graph[110][110];
void topo(int vertex);
int main()
{
int i,j,edge,p,x,y,kk,ff,rr,pp;
while(scanf("%d%d",&vertex,&edge)==2)
{
if((vertex==0)&&(edge==0))
break;
for(ff=1;ff<=vertex;ff++)
for(rr=1;rr<=vertex;rr++)
graph[ff][rr]=0;
for(i=1;i<=edge;i++)
{
scanf("%d%d",&x,&y);
graph[x][y]=1;
}
for(kk=1;kk<=vertex;kk++)
{ indegree1[kk]=0;
strtop[kk]=0;
}
for(i=1;i<=vertex;i++)
for(j=1;j<=vertex;j++)
if(graph[j][i]==1)
indegree1[i]++;
topo(vertex);
for(pp=1;pp<=vertex;pp++)
printf("%d ",strtop[pp]);
printf("\n");
}
return 0;
}
void topo(int vertex)
{
int l,p,xx,node,top=0,d=0;
for(l=1;l<=vertex;l++)
if(indegree1[l]==0)
strtop[++top]=l;
while(d!=vertex)
{
node=strtop[++d];
for(xx=1;xx<=vertex;xx++)
if(graph[node][xx]==1)
{
indegree1[xx]=indegree1[xx]-1;
if(indegree1[xx]==0)
strtop[++top]=xx;
}
}
}
No comments:
Post a Comment