首页 > 代码库 > POJ 2367 Genealogical tree 拓扑题解
POJ 2367 Genealogical tree 拓扑题解
一条标准的拓扑题解。
我这里的做法就是:
保存单亲节点作为邻接表的邻接点,这样就很方便可以查找到那些点是没有单亲的节点,那么就可以输出该节点了。
具体实现的方法有很多种的,比如记录每个节点的入度,输出一个节点之后,把这个节点对于其他节点的入度去掉,然后继续查找入度为零的点输出。这个是一般的做法了,效果和我的程序一样的。
有兴趣的也可以参考下我这种做法。
#include <stdio.h> #include <string.h> #include <vector> using namespace std; const int MAX_N = 101; int N, v; vector<int> gra[MAX_N]; bool vis[MAX_N]; void topologicalSort() { int c = 0; while (c < N) { for (int i = 1; i <= N; i++) { if (vis[i]) continue; bool ind = 0; for (int j = 0; j < (int)gra[i].size(); j++) { if (!vis[gra[i][j]]) { ind = true; break; } } if (!ind) { c++; vis[i] = true; printf("%d ", i); } } } } int main() { while (~scanf("%d", &N)) { for (int i = 1; i <= N; i++) gra[i].clear(); memset(vis, 0, sizeof(vis)); for (int u = 1; u <= N; u++) { while (~scanf("%d", &v) && v) gra[v].push_back(u); } topologicalSort(); putchar('\n'); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。