时间限制: 1000 ms 内存限制: 65536 KB
提交数: 2789 通过数: 2020
【题目描述】
有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。

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

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

【输入】
第1行一个整数NN(1≤N≤1001≤N≤100),表示家族的人数;

接下来NN行,第ii行描述第ii个人的儿子;

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

【输出】
输出一个序列,使得每个人的后辈都比那个人后列出;

如果有多解输出任意一解。

【输入样例】
5
0
4 5 1 0
1 0
5 3 0
3 0
【输出样例】
2 4 5 3 1

#include <iostream>
#define N 128
using namespace std;

int in_deg[N],edgeN;//一维表点 二维表线 edgex 放的是其边的数目 
int n;


inline void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int t;
        while(true)
        {
            cin>>t;
            if(t==0)
                break;
            edget[0]]=i;    //建边 
            in_deg[t]++;
        }
    }
}

inline bool topsort()
{
    int cnt=0; //计算被out的点
    while(cnt<n)
    {
        int start=0;
        for(int i=1;i<=n;i++)
            if(in_deg[i]==0)
            {
                start=i;
                cnt++; 
                //把该点标记删除
                in_deg[i]=-1; 
                break;
            }
        cout<<start<<" ";
        
        //下面开始清理边
        for(int i=1;i<=n;i++)
        {
            int cnt2=0;    //用来记录减少的度 
            for(int j=1;j<=edgei;j++)
                if(edgei==start)    //由被删除点导出的边,应该被删除
                {
                    cnt2++;
                    edgei=0;
                }
             in_deg[i]-=cnt2;
        }
     } 
}

int main()
{
    init();
    topsort();
}
Last modification:February 6th, 2021 at 01:26 am