郑州高新区做网站开发的公司/深圳seo优化排名

原题链接：1004 Counting Leaves (30分)

题目大意：

数一下这个树有几个结点是非叶子结点（有儿子）。
输出的时候在一行中，输出每一层的叶子结点数目。

分析：

1. 邻接表：我们使用邻接表对树进行存储。h 数组代表每一条链子的头，h 数组长度为 n，代表这棵树共有 n 个结点，初始时它们为 -1，代表没有子结点。然后每次增加一个儿子，它就指向它的儿子（注意：除了根节点之外，每一个结点都有一个唯一索引）。
2. 存树：刚开始，初始化 h 数组。每次存一个父子信息的时候，先给这个结点的值放入 e 中（e 代表value），将这个结点的 next 链接到 h 之后，并且让 h 连着这个新的结点（这里相当于在链表中插入一个结点）。
3. 深度优先搜索：就是传统的 DFS。我们对邻接表的每一行插入的时候，新来的元素总会靠近头。记得要记录每次的层数，才能知道深度。

满分代码：

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
typedef long long LL;
using namespace std;
const int MAXN = 1e2+10;
/*n结点总数	m非叶子结点数 优先用DFS 数组h模拟邻接表 
*/
int n, m;
int h[MAXN], e[MAXN], ne[MAXN], idx;
int cnt[MAXN], max_depth;
// 为a添加一个儿子b 
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 第一次u代表根节点 
void dfs(int u, int depth) {// 如果u是叶子结点 if(h[u] == -1) {cnt[depth]++;max_depth = max(max_depth, depth);return;}// 遍历所有从u出发的边 for(int i = h[u]; ~i; i = ne[i]) {dfs(e[i], depth + 1);}
}
int main() {cin >> n >> m;memset(h, -1, sizeof h);for(int i = 0; i < m; i++) {// id代表非叶子结点编号 int id, k;cin >> id >> k;while(k--) {int son;cin >> son;// 为id增加一个son add(id, son);}} 	dfs(1, 0);cout << cnt[0];for(int i = 1; i <= max_depth; i++) {cout << " " << cnt[i];}cout << endl;return 0;
}
/*
5 2
1 3 2 3 4
3 1 5 
*/