英文太短，直接貼
Description
Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:
- No two balls share the same label.
- The labeling satisfies several constrains like "The ball labeled with a is lighter than the one labeled with b".
Can you help windy to find a solution?
Input
The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers a and b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, b ≤ N) There is a blank line before each test case.
Output
For each test case output on a single line the balls' weights from label 1 to label N.
If several solutions exist, you should output the one with the smallest
weight for label 1, then with the smallest weight for label 2, then
with the smallest weight for label 3 and so on... If no solution exists,
output -1 instead.
然后這題是一個裸的拓?fù)渑判颍禽敵鲇悬c忽悠人，要求輸出標(biāo)簽代表的球的重量，按照標(biāo)簽號排序，而且對于重復(fù)情況需要標(biāo)簽ID小的球的質(zhì)量盡量小。
這里有一個錯誤折騰死人，如果按照正向拓?fù)洌o標(biāo)簽號小的標(biāo)簽分配給質(zhì)量小的球是不對的，應(yīng)為對于拓?fù)湫騺碚f，很多鏈?zhǔn)瞧叫械?，給鏈頭元素最小值的貪心策略并不能保證全局最小，如下圖兩條平行鏈，如果給3分配了較小質(zhì)量的球，1就得不到最小質(zhì)量的球，導(dǎo)致結(jié)果不滿組最優(yōu)，
但是如果逆向拓?fù)?，給鏈頭標(biāo)簽最大的分配最重的物體一定能保證正向拓?fù)湫蜃钚?/span>
4 2 5
3 1
1 # include <cstdio>
2 # include <queue>
3 # include <vector>
4 # include <cstring>
5 using namespace std;
6 priority_queue<int,vector<int>,less<int> >q;
7 int g[205],degree[205];
8 int nxt[50000],v[50000],c,n,m;
9 int ans[205],num;
10 int main()
11 {
12 int testcase;
13 scanf("%d",&testcase);
14 while(testcase--)
15 {
16 memset(g,-1,sizeof(g));
17 memset(degree,0,sizeof(degree));
18 c=num=0;
19 while(!q.empty()) q.pop();
20 scanf("%d%d",&n,&m);
21 while(m--)
22 {
23 int a,b;
24 scanf("%d%d",&a,&b);
25 v[c]=a;
26 nxt[c]=g[b];
27 g[b]=c++;
28 degree[a]++;
29 }
30 for(int i=1;i<=n;i++)
31 if(!degree[i])
32 q.push(i);
33 num=n;
34 while(!q.empty())
35 {
36 int top=q.top();
37 q.pop();
38 ans[top]=num--;
39 for(int p=g[top];p!=-1;p=nxt[p])
40 {
41 degree[v[p]]--;
42 if(!degree[v[p]])
43 q.push(v[p]);
44 }
45 }
46 if(num>0)
47 printf("-1\n");
48 else
49 {
50 printf("%d",ans[1]);
51 for(int i=2;i<=n;i++)
52 printf(" %d",ans[i]);
53 printf("\n");
54 }
55 }
56 return 0;
57 }