一条标准的拓扑题解。
我这里的做法就是:
保存单亲节点作为邻接表的邻接点,这样就非常方便能够查找到那些点是没有单亲的节点,那么就能够输出该节点了。
详细实现的方法有非常多种的,比方记录每一个节点的入度,输出一个节点之后,把这个节点对于其它节点的入度去掉,然后继续查找入度为零的点输出。这个是一般的做法了,效果和我的程序一样的。
有兴趣的也能够參考下我这样的做法。
- #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;
- }
来源: http://www.bubuko.com/infodetail-2159231.html