首页 > 代码库 > SDUT3037--让领导先走（拓扑排序）
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必然不同。
输出
对每个测试数据，输出一行排队的顺序，用空格隔开。
示例输入
5 103 51 42 51 23 41 42 31 53 51 2
示例输出
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\n", j);29 ss++;30 break;31 }32 else33 {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 }
SDUT3037--让领导先走（拓扑排序）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。