POJ 3687 Labeling Balls 拓扑排序

这道题是拓扑排序的一个变种， 题目的要求是编号最小的点尽量在前面，而且在满足编号1尽量靠前的条件下，编号2要尽量靠前，在满足前两个条件下，编号3尽量靠前，依次类推。

首先，传统的拓扑排序就无法解决这个问题了，我们只能做到每次尽可能把编号小的点放到前面，但不能保证就是编号1尽量靠前，然后编号2.3等等均尽量靠前。这时就要转变一个方法了。那就是逆序求拓扑序列。每次找到最大的拿出来放到序列的尾部，然后就能达到题目的要求了。

1. 把所有出度为 0 的节点放进优先队列 PQ //这里的优先队列是以数值大的优先
2. WHILE： PQ 不是空队列
3. 从 PQ 中取出编号最大的元素 a，把 a 添加到答案的头部。
4. FOR：所有指向 a 的边 b → a
5. 把 b 的出度减 1。如果 b 的出度变为 0，则把 b 放进优先队列 PQ。

需要注意的是，最后求出的序列只是小球的编号而已，而题目要求是编号升序输出小球的重量。这一点样例很阴险，直接给掩盖过去了。一般不注意就会倒霉在这里。

另外还需要判重，还会出现1,1这种数据，都要考虑到。

/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int n, m;
int out[201];
int ans[201], res[201];
bool used[201][201];
vector<int>v[201];
bool flag;
void topsort()
{
    int i, ct = 0;
    priority_queue<int,vector<int>,less<int> >q;
    for(i = 1; i <= n; i++)
    {
        if(out[i] == 0)
        q.push(i);
    }
    while(!q.empty())
    {
        int first = q.top();
        ans[ct++] = first;
        q.pop();
        int size = v[first].size();
        for(i = 0; i < size; i++)
        {
            int can_reach = v[first][i];
            out[can_reach]--;
            if(out[can_reach] == 0)
            q.push(can_reach);
        }
    }
    if(ct < n) flag = false;
    else if(ct == n) flag = true;
}
int main()
{
#ifdef LOCAL
    freopen("ride.in","r",stdin);
    freopen("ride.out","w",stdout);
#endif
    int t, x, y, i;
    scanf("%d", &t);
    while(t--)
    {
        flag = false;
        bool can = true;
        memset(out, 0, sizeof(out));
        memset(used, false, sizeof(used));
        scanf("%d%d", &n, &m);
        for(i = 0; i <= n; i++)
        v[i].clear();
        for(i = 0; i < m; i++)
        {
            scanf("%d%d", &x, &y);
            if(used[x][y]) continue;
            if(x == y)
            can = false;
            else
            {
                used[x][y] = true;
                v[y].push_back(x);
                out[x]++;
            }
        }
        topsort();
        if(flag && can)
        {
            for(i = n; i >= 1; i--)
            {
                res[ans[i - 1]] = n - i + 1;
            }
            for(i = 1; i < n; i++)
            printf("%d ", res[i]);
            printf("%d\n", res[n]);
        }
        else puts("-1");
    }
    return 0;
}