Poj 3687

题目大意：给出n个球和m个关系，要你根据这些关系求出他们正确的序列，注意这里让你输出的是第i个球在最终序列里的位置。

算法思想：拓扑排序，注意一下反向建图，还有重边要判定一下，最后注意如果这个图是个环或者部分是环，就说明关系有矛盾，就输出-1。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int t,n,m;
int a,b;
bool visited[205],isOver;
int p[205][205];
int sym;
typedef struct Node
{
    int indeer;
    int outdeer;
    int v;
    int now;
    bool operator < (const Node &n1) const
    {
        return n1.v>v;
    }
};
Node nodes[205];
priority_queue<Node>que;
void calc()
{
    int flag=n;
    for(int i=1; i<=n; i++)
    {
        nodes[i].v=i;
        if(nodes[i].indeer==0)
            que.push(nodes[i]);
    }
    if(que.empty())
    {
        isOver=true;//说明图中有环
        return;
    }
    while(!que.empty())
    {
        Node k=que.top();
        que.pop();
        flag--;//整个图没有环，但是，部分图可能有环
        nodes[k.v].now=flag+1;
        for(int i=1; i<=n; i++)
        {
            if(p[i][k.v])
            {
                nodes[k.v].outdeer--;
                nodes[i].indeer--;
                p[i][k.v]=0;
                if(nodes[i].indeer==0)
                    que.push(nodes[i]);
            }

        }

    }
    if(flag!=0)
    {
        isOver=true;
    }
}
int main()
{
    scanf("%d",&t);

    while(t--)
    {
        memset(visited,false,sizeof(visited));
        memset(nodes,0,sizeof(nodes));
        memset(p,0,sizeof(p));
        sym=1;

        isOver=false;
        scanf("%d%d",&n,&m);

        for(int i=0; i<m; i++)
        {
            scanf("%d%d",&a,&b);
            if(p[a][b]==0)
            {
                p[a][b]=1;
                nodes[b].outdeer++;
                nodes[a].indeer++;
            }

        }
        calc();
        if(isOver)
            printf("-1\n");
        else
        {

            for(int i=1; i<n; i++)
            {
                printf("%d ",nodes[i].now);
            }
            printf("%d\n",nodes[n].now);
        }

    }
  return 0;
}