首页 > 代码库 > 拓补排序
拓补排序
让领导先走
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
#include<iostream>#include<string.h>using namespace std;int map[22000][22000];int in[30005];int s[30005],n,m;void tuobu(){ int i,j,k=0; for(i=1;i<=n;i++) { if(in[i]==0) {s[k++]=i; in[i]--; for(j=1;j<=n;j++) { if(map[i][j]==0) { in[j]--; } } } } for(i=0;i<k;i++) { if(i==0) cout<<s[i]; else cout<<" "<<s[i]; }cout<<endl;}int main(){ int i,j,k; while(cin>>n>>m) { int x,y; for(i=1;i<=n;i++) in[i]=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=-1; for(i=0;i<m;i++) {cin>>x>>y; if(map[x][y]==-1) { in[y]++; map[x][y]=0; } } tuobu(); }}
拓补排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。