【图论】sdut3037--让领导先走（拓扑排序）

让领导先走

Time Limit: 2000MS Memory limit: 65536K

题目描述

完啦完啦，公司里发火灾拉，大家快跑啊，再不跑就没命啦。大家不要乱，请按顺序通过消防通道，说到顺序，那么问题来了。

按照中国特色社会主义文化，我们严格贯彻落实一件事，那就是，让领导先走。

现在又n人，从1标号到n。如果a是b的领导的话，就必须让a排在b的前面。

那么你就要安排大家的顺序。我保证一定有解。

输入

多组输入，然后对于每个测试数据，第一行有两个整数n(1 <= n <= 30000)和m(1 <= m <= 100000)，分别表示人数和上下级存在数。

然后m行，每行两个整数a和b，表示有一个a是b的领导。a和b必然不同。

输出

对每个测试数据，输出一行排队的顺序，用空格隔开。

示例输入

示例输出

1 2 3 4 5

拓扑排序，数据比较大，应该用邻接表，不过这个题的后台数据水，用数组也过了。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<queue>
 5 #include<string.h>
 6 #define MAXN 5001
 7 short int mapp[MAXN][MAXN];
 8 int in[MAXN], vis[MAXN];
 9 int n, m;
10 
11 void topo()
12 {
13     int i, j, k, cnt =0, flag=0,ss=0;
14     for(i=1; i<=n; i++)
15     {
16         for(j=1; j<=n; j++)
17         {
18            if(in[j]==0 && !vis[j])
19            {
20                    cnt++;
21                    if(ss==n)
22                 {
23                     flag =1;
24                     break;
25                 }
26                    if(cnt==n)
27                 {
28                     printf("%d
", j);
29                     ss++;
30                     break;
31                 }
32                 else
33                 {
34                     printf("%d ", j);
35                     ss++;
36                 }
37            }
38         }
39         if(flag) break;
40         if(in[i]==0)
41         {
42             for(k=1; k<=n; k++)
43             {
44                 if(mapp[i][k])
45                 {
46                     in[k]--;
47                 }
48             }
49             vis[i]=1;
50         }
51     }
52 }
53 
54 using namespace std;
55 
56 int main()
57 {
58     int x, y, i;
59     while(~scanf("%d%d", &n, &m))
60     {
61         memset(mapp, 0, sizeof(mapp));
62         memset(in, 0, sizeof(in));
63         memset(vis, 0, sizeof(vis));
64         for(i=0; i<m; i++)
65         {
66             scanf("%d%d", &x, &y);
67             if(mapp[x][y]==1);
68             else{
69                 in[y]++;
70                 mapp[x][y] = 1;
71             }
72         }
73         topo();
74     }
75     return 0;
76 }