每条边只解析一次：parent[y]=x 定根，children[x] 记孩子；编号递增扫描 + 严格大于实现并列取小编号，O(n+m)。
OJ: roj
题目 ID: 1336
难度:入门
标签:入门树图论python
创建: 2026-09-30 05:56
更新: 2026-10-05 10:12
题目描述
x y 表示 root、孩子最多的结点 max（若并列取编号最小者），以及 max 的全部孩子（按编号升序输出）。样例：输入第一行 8 7，随后七行 4 1、4 2、1 3、1 5、2 6、2 7、2 8；输出三行为 4、2、6 7 8。
思路
每条边只解析一次：parent[y]=x 记下 children[x] 记下 max（编号递增扫描配合严格大于比较，天然实现并列取小编号），它的孩子必须显式排序后再输出，因为输入不保证有序。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:56
# update_at: 2026-10-12 14:53
# 树的存储：父亲孩子表示法（每个结点记父亲 + 孩子列表）
# 一个结点的两个字段聚合成 Node 对象：父亲、孩子列表。
# 如何使用：
# 1. 读入每条边 (x, y)：node[y].fa = x，node[x].child.append(y)
# 2. 根是唯一 fa == 0 的结点；孩子最多的结点取 child 最长者，并列取编号小的
# 3. 输出它的孩子前先排序——输入不保证有序
import sys
from collections.abc import Iterator
MAXN = 1005 # 题面结点编号 x,y <= 1000，按上界开
class Node:
"""编号 u 的结点：父亲 + 全部孩子（父亲孩子表示法）。"""
def __init__(self) -> None:
self.fa = 0 # 父亲编号，fa == 0 表示还没有人认领它（即根）
self.child: list[int] = [] # 全部孩子编号，输入不保证有序
node: list[Node] = [Node() for _ in range(MAXN)] # node[u]：编号 u 的结点
def pairs(nums: Iterator[int]) -> Iterator[tuple[int, int]]:
"""把 2m 个结点编号按 (父结点, 孩子) 两两成对。"""
return zip(nums, nums)
def find_root(n: int) -> int:
"""根是唯一没当过孩子的点：读入时每个孩子都写了 fa，所以 fa == 0 的就是根。"""
return next(i for i in range(1, n + 1) if node[i].fa == 0)
def find_busiest(n: int) -> int:
"""孩子最多的结点，并列取编号小者：max 只保留第一个最大值，
而 range 递增，所以并列时自然取到编号小的结点。"""
return max(range(1, n + 1), key=lambda v: len(node[v].child))
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
# 每行的 y 是 x 的孩子：x 的孩子表多一条，y 认下父亲 x
for x, y in pairs(data):
node[y].fa = x
node[x].child.append(y)
busiest = find_busiest(n)
print(find_root(n))
print(busiest)
print(*sorted(node[busiest].child)) # 输出要求升序，输入不保证有序
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 10:12
* update_at: 2026-10-12 14:56
*/
// main.cpp：用父亲孩子表示法存树，找根和孩子最多的结点，孩子升序输出。
//
// 每条边 (x, y) 只解析一次：y 认下父亲 x，x 多一个孩子 y。
// 结点的两个字段聚合成 struct：父亲、孩子列表。
// 根是唯一没当过孩子的点（fa == 0）；孩子最多的结点按"编号递增扫描 + 严格大于"取，
// 并列时自然留下编号小的那个。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1005; // 题面结点编号 x,y <= 1000，按上界开
struct Node {
int fa; // 父亲编号，fa == 0 表示还没有人认领它（即根）
vector<int> child; // 全部孩子编号，输入不保证有序
};
Node node[maxn]; // node[u]：编号 u 的结点
ll n, m; // 结点个数、边数
// 读入 m 条边：每条边一次写两处，y 认下父亲，x 多一个孩子
void read_input() {
cin >> n >> m;
for (ll i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
node[y].fa = x;
node[x].child.push_back(y);
}
}
// 根是唯一没当过孩子的点：读入时每个孩子都写了 fa，所以 fa == 0 的就是根
ll find_root() {
for (ll v = 1; v <= n; v++) {
if (node[v].fa == 0) {
return v;
}
}
return 0; // 题面保证输入是一棵树，走到这里说明输入不合法
}
// 孩子最多的结点，并列取编号小者：
// 编号递增扫描配合严格大于，先扫到的小编号一定留得住
ll find_busiest() {
ll best = 1;
for (ll v = 1; v <= n; v++) {
if (node[v].child.size() > node[best].child.size()) {
best = v;
}
}
return best;
}
void solve() {
read_input();
ll root = find_root();
ll busiest = find_busiest();
cout << root << "\n";
cout << busiest << "\n";
// 孩子的输出要求按编号从小到大，输入不保证有序，必须显式排序
sort(node[busiest].child.begin(), node[busiest].child.end());
for (size_t i = 0; i < node[busiest].child.size(); i++) {
if (i > 0) {
cout << " ";
}
cout << node[busiest].child[i];
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}