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

港控/mmm° 2022-06-12 04:22 141阅读 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 ##

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

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

## Sample Input ![copy.gif][]      ##

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

## 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");
        }
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1949&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1949&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1949&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif