1004 Counting Leaves (30 分)
PAT,PTA,PAAT,PTTA,ATP,ATTP… … 最近编码能力直线下降，题嘛也读不懂了，还是刷刷PAT、Atcoder、CF叭！
题意：给你 n n n个节点，其中 m m m个是有儿子的节点。接下来给出 m m m行，每行输入，某个节点，该节点儿子数量，儿子们都是谁。
求这棵树的每一层有多少个带有儿子的节点，顺序输出，空格分割（不含有尾空格）。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> #include<map> #include<queue> #include<vector> using namespace std; #define ll long long int #define INF 0x3f3f3f3f const int maxn = 1e5 + 10; int head[maxn]; int leaf[maxn]; int seniority[maxn]; int deci[maxn]; int cntceng[maxn]; int n, m; int Max = 0; struct edge { int to; int nx; }e[maxn]; int sz = 0; void add(int u, int v) { e[++sz].nx = head[u]; e[sz].to = v; head[u] = sz; } void dfs(int id, int ceng) { cntceng[ceng]++; int cnt = 0; for (int i = head[id]; i != -1; i = e[i].nx) { cnt++; int v = e[i].to; dfs(v, ceng + 1); Max = max(ceng + 1, Max); } if (cnt) seniority[ceng]+=cnt; else return; if (cnt) deci[ceng]++; } int main() { memset(head, -1, sizeof head); memset(leaf, 0, sizeof leaf); memset(deci, 0, sizeof deci); memset(cntceng, 0, sizeof cntceng); memset(seniority, 0, sizeof seniority); scanf("%d %d", &n, &m); int u, v; for (int i = 1; i <= m; i++) { scanf("%d", &u); scanf("%d", &leaf[i]); for (int j = 1; j <= leaf[i]; j++) { scanf("%d", &v); add(u, v); } } /*if (n == 1) { puts("0 0"); return 0; }*/ dfs(1,0); //for (int i = 1; i < maxn; i++) {// check // if (seniority[i] == 0) break; // printf("%d ", seniority[i]); //} //cout << endl; int flag = 0; for (int i = 0; i <= Max; i++) { //cout << seniority[i] << " " << deci[i] << endl; int tmp = cntceng[i] - deci[i]; if (i) cout << " "; cout << tmp; } return 0; } //_CRT_SECURE_NO_WARNINGS /*10 4 01 3 02 03 04 03 2 05 06 05 2 07 08 08 2 09 10 */