Labeling Balls POJ - 3687（阅读理解+逆序拓扑排序）

题意：给定标签的顺序，然后输出的是重量

注意点：

1.http://www.cppblog.com/Davidlrzh/articles/115620.html

大佬博客。

2.我遇到的一些问题：

（1）重边要去除

（2）注意排序的是标签，输出的是重量。

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 210;

int t, n, m, grath[maxn], to[maxn], tx[maxn];
bool re[maxn][maxn];
vector <int> G[maxn];
void tosort()
{
    priority_queue <int> pre;
    for(int i = 1; i <= n; i++) if(!grath[i]) pre.push(i);
    int sum = n;
    while(!pre.empty())
    {
        int a = pre.top(); pre.pop();
        to[sum--] = a;
        for(int i = 0; i < G[a].size(); i++)
        {
            int b = G[a][i];
            if(!(--grath[b])) pre.push(b);
        }
    }
    if(sum > 0)
        printf("-1\n");
    else
    {
        for(int i = 1; i <= n; i++)
        {
            if(to[i])
                tx[to[i]] = i;
        }

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

            if(i < n)
                printf("%d ", tx[i]);
            else
                printf("%d\n", tx[i]);
        }
    }
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        memset(re, false, sizeof(re));
        for(int i = 0; i <= n; i++) G[i].clear(), grath[i] = 0;
        for(int i = 1; i <= m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
//            cout<<a<<" "<<b<<" "<<re[a][b]<<endl;
            if(!re[a][b])
            {
                re[a][b] = true;
                G[b].push_back(a);
                grath[a]++;
            }

        }
        tosort();
    }
    return 0;
}