【题目来源】
https://www.luogu.com.cn/problem/B3644
【题目描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
【输入格式】
第 1 行一个整数 N（1≤N≤100），表示家族的人数。接下来 N 行，第 i 行描述第 i 个人的所有后代编号。每行最后是 0 表示描述完毕。
【输出格式】
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。
【输入样例】
5
0
4 5 1 0
1 0
5 3 0
3 0
【输出样例】
2 4 5 3 1
【算法分析】
● 拓扑排序算法概念
拓扑排序是针对有向无环图（DAG, Directed Acyclic Graph）的一种线性排序算法，使得对于图中的每一条有向边 (u, v)，u 在排序中总是位于 v 的前面。
有向图的拓扑序列详见：https://blog.csdn.net/hnjzsyjyj/article/details/116307687
● 拓扑排序算法步骤
（1）从有向图中选择一个无前驱（即入度为0）的顶点并且输出它。
（2）从图中删除该顶点及所有以它为尾的有向边。
（3）重复上述两步，直至不存在无前驱的顶点。
（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列就是一个拓扑序列。
【算法代码：DFS】
#include <bits/stdc++.h> using namespace std; const int N=105; vector<int> g[N]; int ind[N]; //inDegree bool st[N]; stack<int> stk; int n; void dfs(int u) { st[u]=1; for(int i=0; i<g[u].size(); i++) { int j=g[u][i]; if(!st[j]) dfs(j); } stk.push(u); } int main() { cin>>n; for(int i=1; i<=n; i++) { int x; while(cin>>x && x) { g[i].push_back(x); ind[x]++; } } for(int i=1; i<=n; i++) { if(ind[i]==0) dfs(i); } while(!stk.empty()) { cout<<stk.top()<<" "; stk.pop(); } return 0; } /* in: 5 0 4 5 1 0 1 0 5 3 0 3 0 out: 2 4 5 3 1 */【算法代码：BFS】
#include <bits/stdc++.h> using namespace std; const int maxn=1e3+5; int ind[maxn]; //inDegree vector<int> g[maxn]; int n,x; void topsort() { queue<int> q; for(int i=1; i<=n; i++) { if(ind[i]==0) q.push(i); } while(!q.empty()) { int t=q.front(); q.pop(); cout<<t<<" "; for(int i=0; i<g[t].size(); i++) { int j=g[t][i]; ind[j]--; if(ind[j]==0) q.push(j); } } } int main() { cin>>n; for(int i=1; i<=n; i++) { while(cin>>x && x) { g[i].push_back(x); ind[x]++; } } topsort(); return 0; } /* in: 5 0 4 5 1 0 1 0 5 3 0 3 0 out: 2 4 5 3 1 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/147606147
https://mp.weixin.qq.com/s/so_-vWQKgarQD0XzF0sQaw
https://blog.csdn.net/hnjzsyjyj/article/details/116307687
https://www.cnblogs.com/jyssh/p/18829420
https://www.luogu.com.cn/problem/solution/B3644
https://www.acwing.com/problem/content/3707/
https://www.lanqiao.cn/problems/108/learning/
