思路与算法

建立每个编号的孩子表并统计入度。树根是出现过但入度为0的唯一结点。扫描出现的编号，选孩子数最大、并列编号最小的结点，再将其孩子排序输出。单点按约定编号1处理。

正确性说明

有根树除根外每点恰有一个父亲，根没有父亲，因此入度0恰好定位根。孩子表直接记录题意给出的所有直接孩子；按孩子数降序、编号升序比较即可满足最优与并列规则，最后排序得到要求的孩子顺序。

复杂度

初始化编号数组O(1000)，读边O(n)，寻找根和最大孩子数O(1000)；孩子排序O(n log n)，空间O(1000+n)。

易错点

n是点数而非最大编号，标签可能到1000且不连续。统计的是直接孩子，不是所有后代。并列选择最小标签。单点输出1、1及空第三行。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(1001);
    vector<int> in(1001), exists(1001);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        ++in[y];
        exists[x] = exists[y] = 1;
    }
    if (n == 1) {
        cout << "1\n1\n\n";
        return 0;
    }
    int root = 0, best = 0;
    for (int i = 1; i <= 1000; ++i)
        if (exists[i]) {
            if (!in[i])
                root = i;
            if (!best || a[i].size() > a[best].size())
                best = i;
        }
    sort(a[best].begin(), a[best].end());
    cout << root << "\n" << best << "\n";
    for (int i = 0; i < (int)a[best].size(); ++i)
        cout << (i ? " " : "") << a[best][i];
    cout << "\n";
}