首页 > 代码库 > uva-10305-水题-拓扑排序
uva-10305-水题-拓扑排序
输入n,m,n代表点数,m代表边数(i,j),排序时i在j前面,没出现的点随意排
#include <iostream>#include<stdio.h>#include<math.h>#include<memory.h>using namespace std;const int maxNum = 120;int a, b;int map[maxNum][maxNum];int vis[maxNum];int index2;int res[maxNum];bool topoSort(int row){ vis[row] = -1; for (int i = 1; i <= a; i++) { if (vis[i] == -1 && i != row) continue; else if (map[row][i] == 1 && vis[i] == 0) { topoSort(i); } } res[++index2] = row; vis[row] = 1; return true;}int main(){ while (cin >> a >> b) { if(a == b && b == 0) { return 0; } index2 = 0; memset(map, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); int j, k; for (int i = 0; i < b; i++) { cin >> j >> k; //前向边 map[j][k] = 1; } for (int i = 1; i <= a; i++) { if (vis[i] == 0) topoSort(i); } for (int i = a; i >= 1; i--) { if (i == a) { cout << res[i]; continue; } cout << " " << res[i]; } cout << endl; } return 0;}
uva-10305-水题-拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。