1476 数叶子结点 PAT
作者:
NikoNairre
,
2023-11-09 20:41:20
,
所有人可见
,
阅读 70
C++
#include <iostream>
#include <string.h>
using namespace std;
const int N = 110;
int h[N], ne[N], val[N], idx; //key arrays of a graph
int level[N]; //level[i] means the num of leaves in the (i+1)th level
int n, m;
int num_level; //cal the level num of the tree
void add_edge(int a, int b)
{
val[idx] = b, ne[idx] = h[a], h[a] = idx++ ;
}
void dfs(int c, int lv)
{
if (h[c] == -1) { //this is a leaf node
level[lv]++ ; //count this node
num_level = max(num_level, lv + 1); //cal level_num, +1 because the parameter ranges from 0
return;
}
for (int i = h[c]; i != -1; i = ne[i]) {
int v = val[i];
dfs(v, lv + 1); //dfs child node
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof(h));
while (m-- ) { //read m non-leaf nodes
string num; cin >> num; //using char[] also works
int cur = stoi(num); //to address prefix 0, using string to read num and convert to int
int k; cin >> k; //node cur has k child nodes
while (k-- ) {
string nx; cin >> nx;
int x = stoi(nx);
add_edge(cur, x); //there exists an edge from cur to k
}
}
dfs(1, 0); //dfs root 1 in level 1(the function parameter is minused by 1)
for (int i = 0; i < num_level - 1; i++ ) { //cout num of leaf nodes in level order
cout << level[i] << " ";
}
cout << level[num_level - 1];
// string a = "02";
// int b = stoi(a); //works both for char a[] and string
// cout << b << endl;
}