POJ 3687 Labeling Balls 拓撲排序

代碼如下：

[cpp] 
#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; 
}