家谱树
「题目描述」
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
给出每个人的孩子的信息。
输入一个序列，使得每个人的后辈都比那个人后列出。
「输入」
第一行一个整数（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
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<iostream> using namespace std; int main() { int n; cin>>n; int r[101]={0},c[101]={0},a[101][101]={0}; int tot=0,ans[101]={0},m=0,t; int i,j; for(i=1;i<=n;i++) { cin>>j; while(j!=0) { c[i]++; a[i][c[i]]=j; r[j]++; cin>>j; } } for(i=1;i<=n;i++) if(r[i]==0)ans[++tot]=i; while(m!=n) { t=ans[tot]; cout<<t<<' '; tot--; m++; for(i=1;i<=c[t];i++) { r[a[t][i]]--; if(r[a[t][i]]==0) ans[++tot]=a[t][i]; } } //system("pause"); return 0; } |
Subscribe