A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
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.
The input ends with N being 0. That case must NOT be processed.
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.
2 1 01 1 02
0 1
题目意思：先给你n m两个数 n代表一共有多少节点，m表示下面多少行 然后下面每一行是这样的：
爹的ID k个数 儿子1 儿子2 儿子3 … 儿子k
然后让你求 每一层有多少叶子节点（也就是没儿子的爹 ） 思路很简单： 标记好父亲（pre数组） 标记好儿子（son数组） 然后用queue 层序遍历每一层 把每一层的叶子节点放进vector中 最后顺序输出好了（真正的送分题 ） 这题主要是要记录每一层要pop多少次，毕竟是多叉树，哈哈
#include <bits/stdc++.h> const int maxn=5e5+10; const int mod=1e9+7; #define INF 2147483647 #define PI atan(1)*4 #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define pb push_back #define ss(a) scanf("%s",&a) #define sc(a) scanf("%d",&a) #define scc(a,b) scanf("d",&a,&b) #define sccc(a,b,c) scanf("d%d",&a,&b,&c) using namespace std; int pre[105]; int son[105]; queue <int> cen; vector <int> ans; int n,m,p,s,a; int main() { while(cin>>n>>m) { while(!cen.empty()) cen.pop(); CL(son,0); for(int i=0;i<=100;i++) pre[i]=i; //初始化 while(m--) { cin>>s>>p; for(int i=0;i<p;i++) { cin>>a; pre[a]=s;//a的父亲是s son[s]++;//s这个父亲有儿子 } } int len=1;//这个表示要pop多少次 cen.push(1); while(!cen.empty()) { int flag=0;//这个表示pop到哪里了 int tt=0; while(len>flag) { int now=cen.front();//记录当前队列头 flag++; for(int i=1;i<=n;i++) if(i!=now && pre[i]==now) cen.push(i); if(!son[now])tt++; cen.pop(); } len=cen.size();//记录这层的元素个数（要pop多少次） ans.push_back(tt);//这层叶子节点一共有几个 } for(int i=0;i<ans.size();i++) { if(i!=0)printf(" "); printf("%d",ans[i]); } printf("\n"); } return 0; }