首页 > 代码库 > UVa 10305 - Ordering Tasks 拓扑排序题解
UVa 10305 - Ordering Tasks 拓扑排序题解
Topological Sort题解。本题是简单的入门题目。
Topological Sort的思想很简单,就是按没有入度的点,先输出,然后删除这个点的出度。然后输出下一组没有入度的点。
如何实现也是很简单的:
这里使用邻接表,建图的时候反过来建图,建立一个入度邻接表。
然后使用一个vis数组,记录访问过的节点,也可以根据这个信息知道哪些是已经输出的点,这个时候这些点的入度可以不算为当前入度了。
#include <stdio.h> #include <vector> using std::vector; const int MAX_N = 101; vector<int> gra[MAX_N]; bool vis[MAX_N]; int N, M; void init() { for (int i = 0; i <= N; i++) { gra[i].clear(); vis[i] = false; } } bool getNonPredence(int u) { if (gra[u].empty()) return true; for (int i = 0; i < (int)gra[u].size(); i++) { if (!vis[gra[u][i]]) return false; } return true; } void topological() { int count = 0; while (count < N) { for (int i = 1; i <= N; i++) { if (!vis[i] && getNonPredence(i)) { printf("%d ", i); count++; vis[i] = true; } } } } int main() { int u, v; while (scanf("%d %d", &N, &M) && (N || M)) { init(); for (int i = 0; i < M; i++) { scanf("%d %d", &u, &v); gra[v].push_back(u); //逆向建图:入射邻接表 } topological(); putchar('\n'); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。