题目链接:http://poj.org/problem?id=3687
题意:n个重量为1~n的球,给定一些编号间的重量比较关系,现在给每个球编号,在符合条件的前提下使得编号小的球重量小。(先保证1号球最轻,其次2号……)
如果从前扫的话,当遇到入度为0的点,却不一定是1,这里,我参考了金海峰的分析,从重的开始扫,给最重的附上n,n-1... ...,再去掉重的点连的边。
#include <stdio.h>
#include <string.h> #define MAXN 205 bool g[MAXN][MAXN];
int in[MAXN];
int vis[MAXN]; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(g,false,sizeof(g));
memset(vis,false,sizeof(vis));
memset(in,,sizeof(in)); int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(!g[b][a])
in[a] ++;
g[b][a]=true;
} int ans[MAXN];
bool flag = true;
for(int i=n;i>=;i--)
{
int q = -;
for(int j=n;j>=;j--)
{
if(!vis[j]&&in[j]==)
{
q = j;
break;
}
}
if(q==-)
{
flag = false;
break;
}
vis[q] = true;
ans[q] = i;
for(int j=;j<=n;j++)
{
if(g[q][j])
in[j] --;
}
} if(flag)
{
for(int i=;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
else puts("-1"); }
return ;
}