首页 > 代码库 > 1004. Counting Leaves (30)
1004. Counting Leaves (30)
时间限制
400 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
View Code
Input
Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID‘s of its children. For the sake of simplicity, let us fix the root ID to be 01.
Output
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output "0 1" in a line.
1 #include <iostream> 2 3 using namespace std; 4 5 6 7 struct fun 8 9 { 10 11 int father; 12 13 bool ifdo; 14 15 int h; 16 17 }; 18 19 20 21 fun F[101]; 22 23 24 25 int main() 26 27 { 28 29 30 31 int n; 32 33 while(cin>>n) 34 35 { 36 37 int i; 38 39 for(i=1;i<=n;i++) 40 41 { 42 43 F[i].ifdo=true; 44 45 F[i].h=1; 46 47 F[i].father=-1; 48 49 } 50 51 52 53 int m; 54 55 cin>>m; 56 57 int high=0; 58 59 if(m==0) cout<<1<<endl; 60 61 else 62 63 { 64 65 66 67 int name1,name2,num; 68 69 while(m--) 70 71 { 72 73 cin>>name1>>num; 74 75 76 77 F[name1].ifdo=false; 78 79 for(i=0;i<num;i++) 80 81 { 82 83 cin>>name2; 84 85 F[name2].father=name1; 86 87 } 88 89 90 91 } 92 93 94 95 96 97 /*这题目陷阱在这，每行第一个ID并不是 98 99 从小到大按循序排列的，所以不能在上个循环中直接求h100 101 需要记录父节点 在以下循环中求h；102 103 */104 105 106 107 108 109 for(i=2;i<=n;i++)110 111 {112 113 F[i].h=F[F[i].father].h+1;114 115 if(F[i].h>high) high=F[i].h;116 117 }118 119 120 121 122 123 int j;124 125 bool fir=true;126 127 for(i=1;i<=high;i++)128 129 {130 131 int sum=0;132 133 for(j=1;j<=n;j++)134 135 {136 137 if(F[j].ifdo&&F[j].h==i) sum++;138 139 }140 141 if(fir) cout<<sum;142 143 else cout<<" "<<sum;144 145 fir=false;146 147 }148 149 cout<<endl;150 151 }152 153 154 155 156 157 }158 159 160 161 162 163 return 0;164 165 } 166 167 168
1004. Counting Leaves (30)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。