A family hierarchy is usually presented by a pedigree tree.

一個家族的層次結(jié)構(gòu)經(jīng)常用一個血緣樹來呈現(xiàn)。

Your job is to count those family members who have no child.

你的工作是計(jì)算出沒有孩子的家族成員個數(shù)。

Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100,

每一個輸入文件包含一個測試用例，每一個測試用例由一行開始，包含N，

the number of nodes in a tree, and M (< N), the number of non-leaf nodes.

表示數(shù)節(jié)點(diǎn)的數(shù)目，和一個M，表示不是葉子的節(jié)點(diǎn)

Then M lines follow, each in the format:

接下來M行，每一行格式是這樣的：

ID K ID[1] ID[2] ... ID[K]

where ID is a two-digit number representing a given non-leaf node,

ID是一個兩位數(shù)表示一個被給出的非葉子節(jié)點(diǎn)

K is the number of its children, followed by a sequence of two-digit ID's of its children.

K是它孩子的數(shù)量，接下來一個連續(xù)的兩位數(shù)是它孩子的ID

For the sake of simplicity, let us fix the root ID to be 01.

為了讓問題簡單化，讓我們定義跟節(jié)點(diǎn)ID為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.

對于每一個測試用例，你被要求數(shù)出家族人中沒有孩子，對于每個資歷等級都是由根節(jié)點(diǎn)開始的。

The numbers must be printed in a line, separated by a space,

數(shù)必須在一行打印出，用空格分開

and there must be no extra space at the end of each line.

文件結(jié)尾不能有多余的空格

The sample case represents a tree with only 2 nodes,

樣本測試用例代表一個數(shù)有兩個節(jié)點(diǎn)

where 01 is the root and 02 is its only child.

01是根節(jié)點(diǎn)，02是它唯一的孩子

Hence on the root 01 level, there is 0 leaf node;

因此對于01所在的等級來說，沒有葉子為0的節(jié)點(diǎn)。

and on the next level, there is 1 leaf node. Then we should output "0 1" in a line.

然后對于下一個等級來說，有一個葉子的節(jié)點(diǎn)，所以在一行中輸出“0 1“

Sample Input

2 1 01 1 02

Sample Output

0 1 一開始我看到題目之后的沒什么好的思路。 首先我想到的就是我們用什么去存放這棵樹，結(jié)構(gòu)體數(shù)組鏈表，肯定可以存放所有完整的關(guān)系。 但是當(dāng)我建完結(jié)構(gòu)體之后我就發(fā)現(xiàn)，其實(shí)對于這道題目的輸出來說，父子的關(guān)系并沒有那么重要，尤其是這個父親有那幾個孩子，這個信息基本用不到。 然后就是這個節(jié)點(diǎn)在這顆樹的等級，其實(shí)只要知道自己的父親是誰，自己的父親等級是多少，那么就能知道自己的等級了。 分析完這幾個點(diǎn)之后，下面就是要注意的地方了。 ? 首先我們不能直接在輸入的時候就確定等級，因?yàn)槟爿斎氲臅r候，雖然你知道你父親是誰了，但是你不一定知道你父親的等級是多少，有可能你父親的等級還沒有確定呢。所以我們只能先記錄父親。然后通過后面的循環(huán)去把所有的等級更新一遍。 這也導(dǎo)致了這是這道題時間復(fù)雜度最高的地方了。因?yàn)楹唵纹鹨娢矣昧私Y(jié)構(gòu)體數(shù)組去存放，這樣的存放相比樹來說，更新值就比較麻煩了，需要循環(huán)每個值去更新。所以時間復(fù)雜度就一下到了N^2 如果用樹存放的話一定會好很多。 ? 還有可以優(yōu)化的地方是，可以把最后的求每個等級最后答案的數(shù)組的循環(huán)放在這個N^2里面，這樣還能再快一些。 ? #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<string.h>using namespace std;int result[205]; struct Node {int level;//當(dāng)前節(jié)點(diǎn)所在的等級int flag;//0沒有孩子，1是有孩子int father;//父節(jié)點(diǎn) };int main() {struct Node nodes[205];int n,m,i,j;int nowNode,nowNodeNumber,childNode;int maxLevel=1;cin>>n>>m;//初始化for (i = 0; i <= n; i++){nodes[i].level = 0;nodes[i].flag = 0;nodes[i].father = 0;}nodes[1].level = 1;//輸入并保存關(guān)系while (m--){cin>>nowNode;cin>>nowNodeNumber;if(nowNodeNumber != 0)nodes[nowNode].flag = 1;while (nowNodeNumber--){cin>>childNode;//保存自己的父親是誰nodes[childNode].father = nowNode;}}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){//如果有一個點(diǎn)的父親標(biāo)識是自己，那么它就是你的兒子，那么他的等級，應(yīng)該是你的等級+1if(nodes[j].father == i){nodes[j].level = nodes[i].level + 1;}}}//查詢每一個等級有多少個沒有孩子的點(diǎn)，記錄在result數(shù)組中for (i = 1; i <= n; i++){if(nodes[i].flag != 1 && nodes[i].level > 0)result[nodes[i].level]++;//記錄最大的等級，用于最后的輸出if(nodes[i].level > maxLevel)maxLevel = nodes[i].level;}for (i = 1; i < maxLevel; i++){cout<<result[i]<<" ";}cout<<result[i];return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/linkstar/p/5674895.html

總結(jié)

以上是生活随笔為你收集整理的PAT1004的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。