当前位置: 代码迷 >> 综合 >> 拓扑排序算法(AOV)简单例题 【例4-12】、家谱树
  详细解决方案

拓扑排序算法(AOV)简单例题 【例4-12】、家谱树

热度:76   发布时间:2024-01-15 08:17:33.0

【例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;
}

  相关解决方案