POJ 3687 Labeling Balls 逆向建图，拓扑排序

题目链接： http://poj.org/problem?id=3687

要逆向建图，输入的时候要判重边，找入度为0的点的时候要从大到小循环，尽量让编号大的先入栈，输出的时候注意按编号的顺序输出重量，不是按重量大小输出编号。。

题目确实很简单，但是感觉很经典。

 #include <stdio.h>

 #include <string.h>

 #include <stack>

 using namespace std;

 bool graph[][], vis[];

 int n, m, indegree[], weight[];

 stack<int>s;

 bool toposort()

 {

     while(!s.empty())s.pop();

     memset(vis, , sizeof(vis));

     int cnt = ;

     for(int i = ; i < n; i++)

     {

         for(int j = n; j >= ; j--)

         {

             if(indegree[j] ==  && !vis[j])

             {

                 cnt++;

                 s.push(j);

                 vis[j] = ;

                 for(int k = ; k <= n; k++)

                 {

                     if(graph[j][k])

                         indegree[k]--;

                 }

                 break;

             }

         }

     }

     return cnt == n;

 }

 void solve()

 {

     int w = ;

     while(!s.empty())

     {

         int u = s.top();

         s.pop();

         weight[u] = w++;

     }

     for(int i = ; i < n; i++)

         printf("%d ", weight[i]);

     printf("%d\n", weight[n]);

 }

 int main()

 {

     int t, u, v;

     scanf("%d", &t);

     while(t--)

     {

         scanf("%d %d", &n, &m);

         memset(graph, , sizeof(graph));

         memset(indegree, , sizeof(indegree));

         for(int i = ; i < m; i++)

         {

             scanf("%d %d", &u, &v);

             if(!graph[v][u])

             {

                 graph[v][u] = ;

                 indegree[u]++;

             }

         }

         if(toposort())

             solve();

         else printf("-1\n");

     }

     return ;

 }