題目翻譯
族譜通常能夠顯示一個人在家族中的輩分，你的任務是計算一個家族中沒有孩子的成員的數量，
輸入格式
每一個輸入檔案包含一個測驗樣例，每一個樣例由一行包括0<N<100,樹中節點的個數,和M(<N)，非葉節點的個數，然后接下來的M行的格式如下:
ID K ID[1] ID[2] ... ID[K]
ID是一個兩位數，代表給定的非葉子節點，K是它的孩子的數量，緊接著是一個代表其孩子的兩位數的ID序列，為了簡單起見，讓我們把根節點的ID設為01，
輸入以N為0結尾，那個樣例不用處理，
輸出樣例
對于每一個測驗樣例，你都應該計算從根節點開始每一層中沒有孩子的節點的個數，成員們必須被輸出在一行，由空格分隔開并且行尾沒有多余的空格，
樣例展示一個只有兩個節點的數，01是根節點并且02是它唯一的孩子，因此在根01層有0個葉子節點；然后在下一層有1個葉子節點，所以我們應該在一行輸出0 1，
樣例輸入
2 1
01 1 02
樣例輸出
0 1
分析：這道題大意就是給出了一棵樹，N和M分別代表樹的節點個數和非葉節點個數，然后依次輸入每個非葉節點的編號和它的孩子的個數以及每一個孩子的編號，最后你需要輸出每一層中葉子節點的個數，
很顯然，這是一道關于樹的遍歷的題目，只不過題上并沒有說是二叉樹，所以很可能會出現一個節點有多于2個孩子的情況，這時我們只能選擇用類似于存盤圖的方式來存盤樹了，鑒于題目問的是非葉節點的個數，顯然用鄰接表更方便一點，訪問方式用BFS和DFS都可以，不過我個人覺得DFS寫起來更順手點，不過時間上可能沒有BFS快，我用兩種方法都寫了一遍，AC代碼如下，
DFS
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[100]; //用來存盤樹的二維陣列，用vector可以方便地得到每一行的長度
int maxDepth; //記錄最大深度，輸出的時候可以作為邊界
int cot[100]; //記錄每一層的非葉節點個數
void dfs(int node, int depth);
int main()
{
int n, m;
cin >> n >> m;
//用兩重回圈讀取整棵樹
for (int i = 0; i < m; i++)
{
int node, k;
cin >> node >> k;
for (int i = 0; i < k; i++)
{
int child;
cin >> child;
v[node].push_back(child);
}
}
dfs(1, 0);
for (int i = 0; i < maxDepth; i++)
cout << cot[i] << " ";
cout << cot[maxDepth];
return 0;
}
void dfs(int node, int depth)
{
//遞回基，通過判斷節點所在行的長度來判斷是否是葉節點
if (v[node].size() == 0)
{
cot[depth]++;
maxDepth = max(maxDepth, depth);
return;
}
//用DFS遍歷節點的所有子節點
for (int i = 0; i < v[node].size(); i++)
dfs(v[node][i], depth + 1);
}
BFS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct node
{
int number;
int level;
node(int num, int lel)
{
number = num;
level = lel;
}
};
vector<int> v[100];
int cot[100];
int maxDepth;
void bfs();
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int t, k;
cin >> t >> k;
for (int i = 0; i < k; i++)
{
int child;
cin >> child;
v[t].push_back(child);
}
}
bfs();
for (int i = 0; i < maxDepth; i++)
cout << cot[i] << " ";
cout << cot[maxDepth];
}
void bfs()
{
queue<node> q;
node root(1, 0);
q.push(root);
while (!q.empty())
{
node t = q.front();
q.pop();
if (v[t.number].size() == 0)
{
cot[t.level]++;
maxDepth = max(t.level, maxDepth);
continue;
}
for (int i = 0; i < v[t.number].size(); i++)
{
node child(v[t.number][i], t.level + 1);
q.push(child);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55354.html
標籤：其他
上一篇：快速沃爾什變換小記