#include<stdio.h>
const long maxv=108;
long v,e,count,a[maxv],used[maxv];
bool g[maxv][maxv],ans;
void init()
{
scanf("%ld%ld",&v,&e);
for(long i=1;i<=v;i++)
for(long j=1;j<=v;j++)
g[i][j]=false;
for(long i=1;i<=e;i++)
{
long a,b;
scanf("%ld%ld",&a,&b);
g[a][b]=true;
}
}
void dfs(long now)
{
if(!ans) return;
used[now]=-1;
for(long i=1;i<=v;i++)
if(g[now][i])
{
if(used[i]==-1)
{
ans=false;
return;
}
else if(!used[i])
dfs(i);
}
a[count]=now;count--;
used[now]=1;
}
void toposort()
{
long begin;
ans=false;
for(long i=1;i<=v;i++)
{
for(long j=1;j<=v;j++)
if(g[j][i])
break;
begin=i;
ans=true;
break;
}
// Find a Vertex to Start
if(ans)
{
for(long i=1;i<=v;i++)
used[i]=0;
count=v;
dfs(begin);
}
// Topo_Sort
if(ans)
{
bool first=true;
for(long i=1;i<=v;i++)
{
if(first) first=false;
else putchar(' ');
printf("%ld",a[i]);
}
putchar('\n');
}
else
printf("No answer.\n");
// Write down the Answer
}
int main()
{
//*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
init();
toposort();
return 0;
}
posted on 2010-01-06 17:49
lee1r 閱讀(417)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構