求树的根
时间限制：1 秒
空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
描述
给定一棵包含n nn个节点的有根树，节点编号为1 ∼ n 1 \sim n1∼n。输入以n − 1 n - 1n−1条有向边( a i , b i ) (a_i, b_i)(ai,bi)表示：存在一条从a i a_iai指向b i b_ibi的边，且整棵树构成一棵树。
请输出：
- 树的根节点编号（唯一，入度为0 00）；
- 所有叶子节点编号（出度为0 00），按升序排列。
输入描述
- 第一行输入整数n ( 1 ≤ n ≤ 10 5 ) n\ (1 \le n \le 10^5)n(1≤n≤105)。
- 接下来n − 1 n - 1n−1行，每行输入两个整数a i , b i ( 1 ≤ a i , b i ≤ n ) a_i, b_i\ (1 \le a_i, b_i \le n)ai,bi(1≤ai,bi≤n)，表示一条有向边a i → b i a_i \to b_iai→bi。
输出描述
- 第一行输出根节点编号。
- 第二行输出所有叶子节点编号（升序，空格分隔）。
示例 1
输入：
3 1 2 1 3输出：
1 2 3数据范围与提示
- 1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105
- 1 ≤ a i , b i ≤ n 1 \le a_i, b_i \le n1≤ai,bi≤n
- 输入保证构成一棵有根树，因此入度为0 00的节点恰有一个。
- 核心做法：
- 用两个数组分别统计每个节点的入度与出度；
- 入度为0 00的节点即为根；
- 出度为0 00的节点即为叶子，用
vector收集后一次性输出即可（从小到大枚举节点编号，天然有序，无需额外排序）。
- 边界情况：n = 1 n = 1n=1时没有输入边，此时根与叶子都是节点1 11，需要特判。时间复杂度O ( n ) O(n)O(n)。
解题思路
本题是有根树基本性质统计的入门题。给定一棵有n nn个节点的有根树，边以有向边( a i , b i ) (a_i, b_i)(ai,bi)的形式给出（表示a i a_iai指向b i b_ibi），要求找出根节点（入度为0 00的唯一节点）和所有叶子节点（出度为0 00的节点），并按升序输出叶子编号。只需统计每个节点的入度和出度，即可在线性时间内完成。
1. 问题等价转化
- 有根树中，根节点没有父节点，因此其入度为0 00；其余节点均有且仅有一个父节点，入度为1 11。
- 叶子节点没有子节点，因此其出度为0 00；非叶子节点至少有一个子节点，出度大于0 00。
- 题目保证输入构成一棵合法的有根树，因此入度为0 00的节点恰好有一个，即为根节点。
- 叶子节点可能有多个，需要收集所有出度为0 00的节点，并按编号升序输出。
2. 算法实现
- 输入处理：
- 读入n nn。若n = 1 n = 1n=1，则只有一个节点，它既是根也是叶子，直接输出
1和1。 - 创建两个数组
inDeg和outDeg，大小均为n + 1 n+1n+1，初始化为0 00，分别统计每个节点的入度和出度。 - 循环读入n − 1 n-1n−1条有向边( x , y ) (x, y)(x,y)：
inDeg[y]++（y yy的入度加一）；outDeg[x]++（x xx的出度加一）。
- 读入n nn。若n = 1 n = 1n=1，则只有一个节点，它既是根也是叶子，直接输出
- 寻找根节点：
- 遍历节点编号1 ∼ n 1 \sim n1∼n，找到第一个
inDeg[i] == 0的节点，输出其编号，即为根。
- 遍历节点编号1 ∼ n 1 \sim n1∼n，找到第一个
- 收集叶子节点：
- 创建
vector<ll> leaves。 - 再次遍历节点编号1 ∼ n 1 \sim n1∼n，若
outDeg[i] == 0，则将i ii加入leaves。 - 由于遍历顺序是从小到大，
leaves中元素天然升序，无需额外排序（代码中sort是冗余但无害的）。
- 创建
- 输出叶子：
- 按顺序输出
leaves中的元素，空格分隔，最后换行。
- 按顺序输出
3. 复杂度分析
- 时间复杂度：读入边并统计入度、出度需要O ( n ) O(n)O(n)；遍历节点找根和叶子也是O ( n ) O(n)O(n)。总时间复杂度O ( n ) O(n)O(n)。n ≤ 10 5 n \le 10^5n≤105，完全可行。
- 空间复杂度：需要两个长度为n + 1 n+1n+1的数组和存储叶子的向量，空间复杂度O ( n ) O(n)O(n)。
总结
利用有根树中根节点入度为0 00、叶子节点出度为0 00的性质，只需一次遍历统计度数，即可快速确定根和所有叶子。注意n = 1 n=1n=1的边界情况需特判。该方法简单高效，是树结构基础操作的典型应用。
代码简要说明
solve()函数处理单组数据：- 读入n nn，特判n = 1 n=1n=1。
- 数组
a统计入度，b统计出度。 - 循环n − 1 n-1n−1次读入边，更新
a[y]++和b[x]++。 - 遍历1 ∼ n 1 \sim n1∼n，找到
a[i] == 0输出根。 - 遍历1 ∼ n 1 \sim n1∼n，将
b[i] == 0的节点加入c，排序后输出。
- 主函数调用
solve()，使用快速 I/O。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidsolve(){ll n;cin>>n;if(n==1){cout<<"1\n1\n";return;}vector<ll>a(n+1,0);vector<ll>b(n+1,0);for(ll i=1;i<n;i++){ll x,y;cin>>x>>y;a[y]++;b[x]++;}for(ll i=1;i<=n;i++){if(a[i]==0){cout<<i<<'\n';break;}}vector<ll>c;for(ll i=1;i<=n;i++)if(b[i]==0)c.push_back(i);sort(c.begin(),c.end());for(ll i=0;i<=(ll)c.size()-1;i++)cout<<c[i]<<' ';cout<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}