6-15 给任务排序 uva10305

拓扑排序的水题

有关dfs的很好的题

其中c数组的三个状态十分巧妙

还有各种bool的运用

储存答案的方式！！：ans[--t]=x;

因为dfs是先将所有的步骤全部进行完最后开始疯狂存答案在这个dfs主程序进行的过程中遇到有向环则退出

#include<bits/stdc++.h>
using namespace std;
 int n,m,t;
int m1[105][105];
int ans[1000];
int c[1000];


bool  dfs(int x)
{
    c[x]=-1;
    for(int j=1;j<=n;j++)
      if(m1[x][j])
      {
          if(c[j]<0)return false;
           else  if(!c[j])dfs(j);

      }
        c[x]=1;
     ans[--t]=x;

     return true;


}




bool ttt()
{
     t=n;
    for(int i=1;i<=n;i++)
    {
        if(!c[i])
            if(!dfs(i))return false;

    }
    return true;

}



int main()
{


    while(cin>>n>>m,n||m)
    {
        memset(m1,0,sizeof(m1));
        memset(c,0,sizeof(c));
      for(int i=1;i<=m;i++)
      {
          int a,b;cin>>a>>b;
          m1[a][b]=1;

      }
        if(ttt())
        {
            for(int i=0;i<n;i++)
            {
                if(i==0)printf("%d",ans[i]);else printf(" %d",ans[i]);

            }
            printf("
");
        }
        else printf("-1
");


    }





    return 0;
}

View Code

上面的代码是不严谨的！！！

dfs函数里要改为

else if(!c[j]&&!dfs(j))return false;

否则dfs函数永远是true （在这题影响不大因为所有数据都是有效的）