Labeling Balls（poj 3687）

题意：N个球，从1～N编号，质量不同，范围1～N，无重复。给出小球间的质量关系（<), 要求给每个球贴标签，标签表示每个球的质量。按编号输出每个球的标签。如果解不唯一，按编号小的质量小排。

/*

  被这道题坑惨了，刚开始读错题了，题目要求输出每个球的重量，而不是按重量输出球的编号

  还有，因为题目要求如果有多解，则编号小的质量小，因为拓扑排序是按质量从小到大来找，

  所以没有什么好的方法，于是反向拓扑，并且倒着找，把质量大的留给编号大的就可以了。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 210

#define M 40010

using namespace std;

int head[N],out[N],vis[N],a[N],n,m;

struct node

{

    int v,pre;

};node e[M];

void add(int i,int x,int y)

{

    e[i].v=y;

    e[i].pre=head[x];

    head[x]=i;

}

void work()

{

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

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

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(i,y,x);out[x]++;

    }

    int tot=n;

    while()

    {

        int k=;

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

          if(!out[i]&&!vis[i])

          {

              a[i]=tot--;

              vis[i]=;

              k=i;

              break;

          }

        if(!k)break;

        for(int i=head[k];i;i=e[i].pre)

          if(out[e[i].v])out[e[i].v]--;

    }

    if(tot)printf("-1");

    else

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

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

    printf("\n");

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        memset(e,,sizeof(e));

        memset(head,,sizeof(head));

        memset(out,,sizeof(out));

        memset(vis,,sizeof(vis));

        work();

    }

    return ;

}