https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1246

题意就是最普通的拓扑排序，输出可能的排序结果。

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn = 1000; 5  6 int n, m, cuv[maxn][maxn], c[maxn], topo[maxn], t; 7  8 bool dfs(int u) 9 {10     c[u] = -1; 11     for (int v = 1; v<=n; v++) if (cuv[u][v])12     {13         if (c[v]<0) return false;  //存在有向环。 14         else if (!c[v] && !dfs(v)) return false;15     }16     c[u] = 1; topo[--t] = u;17     return true;18 }19 20 bool toposort()21 {22     t = n;23     memset(c, 0, sizeof(c));24     for (int u = 1; u <= n; u++) if (!c[u])25     if (!dfs(u)) return false;26     return true;27 }28 29 int main()30 {31     while (cin >> n >> m && n)32     {33         memset(cuv, 0, sizeof(cuv));34         for (int i = 1; i <= m; i++)35         {36             int u, v;37             cin >> u >> v;38             cuv[u][v] = 1;39         }40         if (toposort())41         {42             for (int i = 0; i < n - 1; i++)43                 cout << topo[i] << " ";44             cout << topo[n - 1] << endl;45         }46         else47             printf("No\n");48     }49     return 0;50 }
      
     

2016-12-11   10:42:03