P4876 找树根和孩子（入门）

解题思路

第一步，理解输入。 先给 n（结点个数）和 m（边数），然后 m 行每行给 x y，表示 y 是 x 的孩子。要找树根、孩子最多的结点，以及它的孩子列表。

第二步，记录父亲和孩子。 用 par[y]=x 记录 y 的父亲；用 chn[x] 记录 x 有几个孩子；用二维数组 chl[x] 存 x 的每个孩子；用 used[i] 标记结点 i 在边里出现过，用来判断哪些编号是真实结点。

第三步，找树根。 树根没有父亲。从小到大扫描编号，第一个"出现过且父亲是 0"的结点就是根。因为树里只有根没有父亲，其它结点（包括叶子）都有父亲。

第四步，找孩子最多的结点。 扫描所有出现过的结点比较 chn[i]，用"严格大于"更新答案，孩子数一样多时保留编号更小的结点，满足题目"多个最大取编号小"的要求。

第五步，输出孩子。 把孩子列表用 sort 从小到大排序后输出。

举个例子。 样例边 4→1、4→2、1→3、1→5、2→6、2→7、2→8。根是 4；结点 2 有 6、7、8 三个孩子最多；排序后输出 6 7 8，与样例一致。

边界情况。 编号最大 1000，数组开到 1005；孩子最多 n-1 个，二维第二维开到 105 足够。mx 先设为根，保证程序总有答案。

参考代码

// 找树根和孩子：统计父亲与孩子，没父亲且出现的结点是根，孩子最多编号小优先
#include <iostream>
#include <algorithm>
using namespace std;

int par[1005];       // 父亲编号，0表示没有
int chn[1005];       // 每个结点的孩子数量
int chl[1005][105];  // 每个结点的孩子列表
int used[1005];      // 是否在边中出现过

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        used[x] = used[y] = 1;
        par[y] = x;
        chl[x][chn[x]++] = y;   // 把 y 加入 x 的孩子
    }
    int root = 1;
    for (int i = 1; i <= 1000; i++)
        if (used[i] && par[i] == 0) { root = i; break; }  // 没父亲的根
    int mx = root;
    for (int i = 1; i <= 1000; i++)
        if (used[i] && chn[i] > chn[mx]) mx = i;  // 孩子最多的结点
    sort(chl[mx], chl[mx] + chn[mx]);             // 孩子按编号从小到大
    cout << root << endl;
    cout << mx << endl;
    for (int i = 0; i < chn[mx]; i++) {
        if (i) cout << ' ';
        cout << chl[mx][i];
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度。 读入 m 条边 O(m)，扫描 1000 个编号找根和最大结点 O(1000)，对孩子排序 O(k log k)，k 是一个结点的孩子数。m 最大 200，整体非常快。

空间复杂度。 数组大小与最大编号 1000 有关，二维孩子数组 O(1000×105)，约 100KB，非常小。