本文主要是介绍拓扑排序算法（AOV）简单例题 【例4-12】、家谱树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【例4-12】、家谱树
【问题描述】
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输出一个序列，使得每个人的后辈都比那个人后列出。
【输入格式】
第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
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define N 105
int n;
int a[N][N],ans[N],r[N],c[N],tot,num;
int main()
{scanf("%d",&n); int j;for(int i=1;i<=n;i++){do{scanf("%d",&j);if(j!=0){c[i]++; //出度+1a[i][c[i]]=j;r[j]++; //入度+1}}while(j!=0);}for(int i=1;i<=n;i++)if(r[i]==0)ans[++tot]=i;//记录入度为0的点，并将所有大的入栈int num=0;do{int t=ans[tot];cout<<t<<" ";//栈顶元素出栈并输出tot--;num++;for(int i=1;i<=c[t];i++){r[a[t][i]]--;if(r[a[t][i]]==0)//入度为0，后继点入栈ans[++tot]=a[t][i];}}while(num!=n);return 0;
}
这篇关于拓扑排序算法（AOV）简单例题 【例4-12】、家谱树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
