1351：【例4-12】家谱树
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
【输入】
第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
1. // 示例代码 拓扑排序算法 2. #include <iostream> 3. #include <stack> 4. #include <vector> 5. using namespace std; 6. 7. const int N = 105; // 定义常量 N，表示数组大小 8. int n, a, c[N], r[N]; // n：图的结点数量，a：当前读入的边的终点序号，c 数组记录每个结点的出度，r 数组记录每个结点的入度 9. vector<int> vn[N]; // 邻接表，记录每个结点的所有后继结点 10. stack<int> ans; // 记录拓扑排序的结果，栈顶的元素表示拓扑排序中最先被访问的结点 11. 12. int main() { 13. cin >> n; 14. for (int i = 1; i <= n; i++) { // 读入图的邻接表，计算每个结点的入度和出度 15. while (cin >> a) { 16. if (a == 0) break; // 遇到 0，表示 i 结点的邻接链表读取完毕 17. vn[i].push_back(a); // 将 i 的一个邻接结点 a 添加到邻接表中 18. c[i]++; // i 的出度加一 19. r[a]++; // a 的入度加一 20. } 21. } 22. 23. for (int i = 1; i <= n; i++) // 找到所有入度为 0 的初始结点，放入拓扑排序的起点集合 24. if (!r[i]) ans.push(i); 25. 26. while (!ans.empty()) { // 对起点集合中的每个结点进行拓扑排序 27. int t = ans.top(); // 取出栈顶的结点作为当前要访问的结点 28. cout << t << " "; // 输出该结点 29. ans.pop(); // 将该结点从栈中弹出 30. for (int i = 0; i < c[t]; i++) { 31. r[vn[t][i]]--; // 后继结点的入度减一 32. if (r[vn[t][i]] == 0) // 如果该后继结点的入度已经为 0，则将其添加到起点集合中 33. ans.push(vn[t][i]); 34. } 35. } 36. 37. return 0; 38. }
