立志用最少的代碼做最高效的表達(dá)

---

PAT甲級(jí)最優(yōu)題解——>傳送門

---

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

Input Specification:
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.

Output Specification:
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

---

題意與分析

題意：
輸入節(jié)點(diǎn)數(shù)、非葉子節(jié)點(diǎn)數(shù)， 接下來(lái)m行，每行給出每個(gè)非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)，最后輸出樹(shù)的每層葉子節(jié)點(diǎn)個(gè)數(shù)。

分析：
DFS、BFS皆可。
DFS簡(jiǎn)單些，
如果使用BFS，需要定義數(shù)組保存每個(gè)節(jié)點(diǎn)所在的層數(shù)。

---

代碼一：DFS解法

#include<bits/stdc++.h> using namespace std;//嵌套vector相當(dāng)于二維數(shù)組 //按層數(shù)DFS遍歷，每深入一次，層數(shù)+1。統(tǒng)計(jì)該層葉子節(jié)點(diǎn)即可 vector<vector<int>>tree(100); //下標(biāo)存儲(chǔ)節(jié)點(diǎn)編號(hào)，內(nèi)容存儲(chǔ)兒子節(jié)點(diǎn)編號(hào) int Level_leave[100], maxLevel = -1; //每層葉子結(jié)點(diǎn)數(shù)、最大層數(shù) int N, M;void DFS(int v, int level) { //深度優(yōu)先遍歷 maxLevel = max(level, maxLevel); //更新最大層數(shù)if(tree[v].empty())++Level_leave[level];for(int i : tree[v]) //不是葉節(jié)點(diǎn)DFS(i, level+1); //遍歷兒子節(jié)點(diǎn) }int main() {cin >> N >> M; while(M--) {int id, k;cin >> id >> k;while(k--) {int iid; cin >> iid;tree[id].push_back(iid);}}DFS(1, 0); for(int i = 0; i <= maxLevel; i++) printf("%s%d", i==0?"":" ", Level_leave[i]);return 0; }

---

代碼二：BFS解法

#include<bits/stdc++.h> using namespace std;vector<vector<int>>tree(110); //加上限定范圍相當(dāng)于二維數(shù)組 int n, m, siz; int leave_level[110]; //每層葉子節(jié)點(diǎn)個(gè)數(shù) int maxLevel = -1, level[110] = {0}; //最大層數(shù)，每個(gè)節(jié)點(diǎn)所在層數(shù) void BFS(int id) {queue<int>q;q.push(id);while(!q.empty()) {int temp = q.front();q.pop();maxLevel = max(maxLevel, level[temp]); //更新最大層數(shù)if(tree[temp].empty())++leave_level[level[temp]]; //遞增該節(jié)點(diǎn)所處層數(shù)下的葉節(jié)點(diǎn)數(shù)目for(int i : tree[temp]) {level[i] = level[temp] + 1; //兒子節(jié)點(diǎn)層數(shù)為父親節(jié)點(diǎn)層數(shù)+1 q.push(i);} } }int main() {scanf("%d%d", &n, &m);while(m--) {int x, k; scanf("%d%d", &x, &k);while(k--) {int v; scanf("%d", &v);tree[x].push_back(v);} }BFS(1);for(int i = 0; i <= maxLevel; i++) printf("%s%d", i==0?"":" ", leave_level[i]);return 0; }

---

每日好句

你的潛意識(shí)，正在操控你的人生，而你卻稱其為命運(yùn)。

總結(jié)

以上是生活随笔為你收集整理的【两种解法】1004 Counting Leaves (30 分)_27行代码AC的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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