学步园

题目地址：http://poj.org/problem?id=3687

代码如下：

 

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;


const int N=210;
typedef long long LL;
int n,m;

int vis[N][N],ru[N];

void topsort()
{
    int i,j,k=n;
    int cnt[N];
    priority_queue<int>q;
    for(i=1;i<=n;i++)
        if(ru[i]==0)
            q.push(i);
    while(!q.empty())
    {
        int t=q.top();
        q.pop();
        cnt[t]=k--;
        for(i=1;i<=n;i++)
        {
            if(vis[i][t])
            {
                ru[i]--;
                if(ru[i]==0)
                    q.push(i);
            }
        }
    }
    if(k!=0)
        printf("-1\n");
    else
    {
        for(i=1;i<n;i++)
            printf("%d ",cnt[i]);
        printf("%d\n",cnt[n]);
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(ru,0,sizeof(ru));
        scanf("%d%d",&n,&m);
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(vis[a][b]==0)
            {//判重
                vis[a][b]=1;
                ru[a]++;
            }
        }
        topsort();
    }
    return 0;
}