拓扑排序(深度优先) C 代码

拓扑排序(深度优先) C 代码

#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;
}