[置顶]Labeling Balls--poj3687

绝地灬酷狼 2022-08-04 08:58 135阅读 0赞

Labeling Balls

<table style="margin-left: auto; margin-right: auto;"> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;12273</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3516</td> 
  </tr> 
 </tbody> 
</table>

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:

1.  No two balls share the same label.
2.  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.

Sample Input

5
    
    4 0
    
    4 1
    1 1
    
    4 2
    1 2
    2 1
    
    4 1
    2 1
    
    4 1
    3 2

Sample Output

1 2 3 4
    -1
    -1
    2 1 3 4
    1 3 2 4
    
    
    
    
    这是一个拓扑题，还不是普通的拓扑，这必须要反向建图+逆向输出，并且注意，这个题让输出的是各个人的位置！！！

1 #include <iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 
     5 using namespace std;
     6 int map[250][250];
     7 int degree[250];
     8 void topo(int n)
     9 {
    10     int i,j,mark,que[250];
    11     for(i=n;i>=0;i--)
    12     {
    13         int x=0;//标记看是否满足要求
    14         for(j=n;j>=0;j--)
    15         {
    16             if(degree[j]==0)
    17             {
    18                 x=1;
    19                 mark=j;
    20                 break;
    21             }
    22         }
    23         if(x==0)
    24             break;
    25         que[mark]=i;
    26         degree[mark]=-1;
    27         for(j=1;j<=n;j++)
    28         {
    29             if(map[mark][j])
    30                 degree[j]--;
    31         }
    32     }
    33     if(i!=-1)
    34         printf("-1\n");
    35     else
    36     {
    37         printf("%d",que[1]);
    38         for(i=2;i<=n;i++)
    39         printf(" %d",que[i]);
    40         printf("\n");
    41 
    42     }
    43 }
    44 
    45 int main()
    46 {
    47     int N,i,m,n,a,b;
    48     scanf("%d",&N);
    49     while(N--)
    50     {
    51         memset(map,0,sizeof(map));
    52         memset(degree,0,sizeof(degree));
    53         scanf("%d%d",&n,&m);
    54         for(i=0;i<m;i++)
    55         {
    56             scanf("%d%d",&a,&b);
    57             if(!map[b][a])//避免重复录入
    58             {
    59                 map[b][a]=1;
    60                 degree[a]++;//反向建图
    61             }
    62         }
    63         topo(n);
    64     }
    65     return 0;
    66 }