WUST 1949 家谱树（拓扑排序+dfs）-蒲公英云

WUST 1949 家谱树（拓扑排序+dfs）

港控/mmm° 2022-06-12 04:22 241阅读 0赞

1949: 家谱树

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld
Submitted: 7 Accepted: 5
[ Submit][ Status][ Web Board]

Description

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。

给出每个人的孩子的信息。

输出一个序列，使得每个人的后辈都比那个人后列出。

Input

多组测试数据。

第1行一个整数N（1<=N<=100），表示家族的人数。

接下来N行，第I行描述第I个人的儿子。

每行最后是0表示描述完毕。

Output

输出一个序列，使得每个人的后辈都比那个人后列出。

如果有多解，输出时序号越小的越在前。

" class="reference-link">Sample Input

Sample Output

2 4 5 3 1
1 2 3 4 5 7 9 10 11 6 8 12

[ Submit][ Status][ Web Board]

题解：

这题真是醉了，那么简单的一题学了我半天，原因是网上的题解都是输出任意一个解就行，我们学校居然要输出序号最小的解。。。不过还是好好学了拓扑排序的，所谓拓扑排序，就是给你一堆数据，给你这些数据的类似于大小关系的二元关系（不形成环），让你给他们按关系从大到小（或者从小到大）进行排序，思路就是找一个出度为0的点，然后把它输出来，并把与他有关系的关系都去掉（去掉一些数据的出度），寻找下一个出度为0的点。。循环就找完了。。而这题是一个极品，不能用常规方法做，我就直接dfs了。。

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<deque>
using namespace std;
int vis[105];//存该点有没有被输出过
int a[105][105];//存每一个点的儿子
int num[105],n,tag;//num计算每一个点的儿子数目
void dfs(int ans)//ans记入输出了几个点
{
    if(ans>=n||tag)//只要找到一个就全停
    {
        tag=1;
        return;
    }
    int i,j;
    int p[105];
    memset(p,0,sizeof(p));//初始化为0，如果还没输出的点中出现了这个点是他的儿子则这个点不能用
    for(i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            for(j=0;j<num[i];j++)//对每一个点的儿子进行遍历覆盖
            {
                p[a[i][j]]=1;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(!p[i]&&!vis[i])//找到一个没有输出的点里面没人是他的爸爸就输出，hhhh这句话有点好笑
        {
            if(ans==0)
            {
                printf("%d",i);
            }
            else
                printf(" %d",i);
            vis[i]=1;//输出过了
            break;
        }
    }
    dfs(ans+1);//很好，下一个
}
int main()
{
    int x,i,j,tot,sum;
    while(scanf("%d",&n)!=EOF)
    {
        tag=0;
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        for(i=1;i<=n;i++)
        {
            while(scanf("%d",&x)&&x)
            {
                a[i][num[i]]=x;
                num[i]++;
            }
        }
        dfs(0);
        printf("\n");
    }
}