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

又如：

重新遍歷計(jì)算層數(shù)解析：孩子的level一定是父親的level+1，這個(gè)是顯然的。03 1 07 02 3 04 05 06 01 2 02 03 我第一行輸入的是3號(hào)結(jié)點(diǎn)，第二行輸入的2號(hào)結(jié)點(diǎn)，第三行輸入的是根結(jié)點(diǎn)，根據(jù)這個(gè)輸入順序就不好判斷3到底是第幾層了。

隊(duì)列解析：剛開始，跟結(jié)點(diǎn)入隊(duì)，就是1入隊(duì)。然后進(jìn)入while，判斷隊(duì)列是不是空，發(fā)現(xiàn)不是空，進(jìn)入循環(huán)體，然后隊(duì)列元素出隊(duì)，返回u 這個(gè)u是樹里邊結(jié)點(diǎn)的編號(hào)，u現(xiàn)在是1，就是根結(jié)點(diǎn)。curlev是當(dāng)前這個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn))的層號(hào)，tree[u].lev是u號(hào)節(jié)點(diǎn)的層號(hào)，curlev和lev都是0，然后跳過(guò)if，執(zhí)行下面的東西。if(tree[u].k==0)是判斷當(dāng)前這個(gè)節(jié)點(diǎn)的孩子數(shù)量是不是0，如果是0就當(dāng)然是葉子節(jié)點(diǎn)了。這里因?yàn)楦?jié)點(diǎn)有兩個(gè)孩子2和3，所以不是葉子節(jié)點(diǎn)，然后底下那個(gè)for循環(huán)是依次讓當(dāng)前節(jié)點(diǎn)的孩子入隊(duì)，就是把根結(jié)點(diǎn)的所有孩子依次入隊(duì)，現(xiàn)在隊(duì)列里是2和3。這樣第一遍循環(huán)就完了，再?gòu)念^開始。現(xiàn)在隊(duì)列的元素是2和3，隊(duì)列不為空，執(zhí)行下面的循環(huán)體。u=q.front()得到隊(duì)頭元素，u=2，是第02號(hào)結(jié)點(diǎn)。然后curlev=1，是02結(jié)點(diǎn)的層數(shù)，這里if判斷curlev和lev不相等,不相等了，說(shuō)明遍歷到下一層了，這時(shí)候就執(zhí)行if底下的代碼，輸出cnt，就是上一層的葉子結(jié)點(diǎn)數(shù)量，是0,然后讓cnt=0，重新統(tǒng)計(jì)現(xiàn)在這層的葉子結(jié)點(diǎn)，并讓lev=curlev，更新lev，代表遍歷到這層了。再下面的if是判斷u這個(gè)結(jié)點(diǎn)是不是葉子結(jié)點(diǎn)，02號(hào)有3個(gè)孩子，不是葉子結(jié)點(diǎn)，cnt不++。然后下面的for是把02號(hào)的3個(gè)孩子依次入隊(duì)。現(xiàn)在隊(duì)列的元素是3 4 5 6。第三次進(jìn)入while循環(huán)，不為空，q.front()得到隊(duì)頭，是3號(hào)結(jié)點(diǎn)，并出隊(duì)。判斷curlev和lev是不是相等的，此時(shí)兩個(gè)都是1，相等跳過(guò)if。判斷3是不是葉子結(jié)點(diǎn)，因?yàn)?有一個(gè)孩子不是葉子結(jié)點(diǎn)，然后把3號(hào)結(jié)點(diǎn)的所有孩子入隊(duì)，就是把7入隊(duì)。此時(shí)隊(duì)列元素是4 5 6 7。然后循環(huán)再開始，隊(duì)列不空，繼續(xù)得到隊(duì)頭元素是4號(hào)結(jié)點(diǎn)，q.pop()出隊(duì)，curlev這時(shí)候是04號(hào)結(jié)點(diǎn)的層數(shù)，是2，而lev是1，此時(shí)兩個(gè)不等，不相等就要打印結(jié)果了cnt=0，打印0，并把step更新，step=2了，然后判斷04號(hào)是不是葉子結(jié)點(diǎn)，發(fā)現(xiàn)04號(hào)的k是0，說(shuō)明他是葉子結(jié)點(diǎn)，cnt++，因?yàn)閗是0，所以下面的for就不執(zhí)行了，現(xiàn)在隊(duì)列的元素是5 6 7，然后這三個(gè)元素的執(zhí)行過(guò)程和4號(hào)結(jié)點(diǎn)是一樣的，略。最后隊(duì)列是空了，退出while循環(huán)，底下有一句打印cnt，就是把最后一層的葉子結(jié)點(diǎn)數(shù)量打印出來(lái)。