1004. Counting Leaves (30)

http://blog.csdn.net/xkzju2010/article/details/46868273

A family hierarchy is usually PResented by a pedigree tree. Your job is to count those family members who have no child.

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. Sample Input

2 1 01 1 02

Sample Output

0 1 1082/5000

Sample Input 2 1 01 1 02 Sample Output 0 1

又如：

重新遍历计算层数解析：孩子的level一定是父亲的level+1，这个是显然的。03 1 07 02 3 04 05 06 01 2 02 03 我第一行输入的是3号结点，第二行输入的2号结点，第三行输入的是根结点，根据这个输入顺序就不好判断3到底是第几层了。

队列解析：刚开始，跟结点入队，就是1入队。然后进入while，判断队列是不是空，发现不是空，进入循环体，然后队列元素出队，返回u 这个u是树里边结点的编号，u现在是1，就是根结点。curlev是当前这个结点(根结点)的层号，tree[u].lev是u号节点的层号，curlev和lev都是0，然后跳过if，执行下面的东西。if(tree[u].k==0)是判断当前这个节点的孩子数量是不是0，如果是0就当然是叶子节点了。这里因为根节点有两个孩子2和3，所以不是叶子节点，然后底下那个for循环是依次让当前节点的孩子入队，就是把根结点的所有孩子依次入队，现在队列里是2和3。这样第一遍循环就完了，再从头开始。现在队列的元素是2和3，队列不为空，执行下面的循环体。u=q.front()得到队头元素，u=2，是第02号结点。然后curlev=1，是02结点的层数，这里if判断curlev和lev不相等,不相等了，说明遍历到下一层了，这时候就执行if底下的代码，输出cnt，就是上一层的叶子结点数量，是0,然后让cnt=0，重新统计现在这层的叶子结点，并让lev=curlev，更新lev，代表遍历到这层了。再下面的if是判断u这个结点是不是叶子结点，02号有3个孩子，不是叶子结点，cnt不++。然后下面的for是把02号的3个孩子依次入队。现在队列的元素是3 4 5 6。第三次进入while循环，不为空，q.front()得到队头，是3号结点，并出队。判断curlev和lev是不是相等的，此时两个都是1，相等跳过if。判断3是不是叶子结点，因为3有一个孩子不是叶子结点，然后把3号结点的所有孩子入队，就是把7入队。此时队列元素是4 5 6 7。然后循环再开始，队列不空，继续得到队头元素是4号结点，q.pop()出队，curlev这时候是04号结点的层数，是2，而lev是1，此时两个不等，不相等就要打印结果了cnt=0，打印0，并把step更新，step=2了，然后判断04号是不是叶子结点，发现04号的k是0，说明他是叶子结点，cnt++，因为k是0，所以下面的for就不执行了，现在队列的元素是5 6 7，然后这三个元素的执行过程和4号结点是一样的，略。最后队列是空了，退出while循环，底下有一句打印cnt，就是把最后一层的叶子结点数量打印出来。