首页 > 代码库 > UVA Ordering Tasks (经典拓扑排序)
UVA Ordering Tasks (经典拓扑排序)
题意:n个任务,m组数据,每组数据输入x,y代表如果想要完成y任务需要先完成x任务,最后输出任务的完成顺序。
经典的拓扑排序。
代码:
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> using namespace std; int map[105][105]; int num[105]; int n,m; int a[101]; void tp() { queue<int>q; for(int i=1;i<=n;i++) { if(num[i] == 0) { q.push(i); } } int t; int e = 0; while(!q.empty()) { t = q.front(); a[e++] = t; q.pop(); num[t]--; for(int j=1;j<=n;j++) { if(map[t][j] == 1) { num[j]--; if(num[j] == 0) { q.push(j); } } } } for(int i=0;i<e;i++) { if(i<e-1) { printf("%d ",a[i]); } else { printf("%d\n",a[i]); } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n == 0 && m == 0) { break; } for(int i=1; i<=n; i++) { num[i] = 0; for(int j=1; j<=n; j++) { map[i][j] = 0; } } int x,y; for(int i=0; i<m; i++) { scanf("%d%d",&x,&y); if(map[x][y] == 0) { map[x][y] = 1; num[y]++; } } tp(); } return 0; }
UVA Ordering Tasks (经典拓扑排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。