求树的根【牛客tracker 每日一题】

求树的根

时间限制：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的节点恰有一个。
• 核心做法：
  1. 用两个数组分别统计每个节点的入度与出度；
  2. 入度为0 00的节点即为根；
  3. 出度为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. 算法实现

1. 输入处理：
   • 读入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的出度加一）。
2. 寻找根节点：
   • 遍历节点编号1 ∼ n 1 \sim n1∼n，找到第一个inDeg[i] == 0的节点，输出其编号，即为根。
3. 收集叶子节点：
   • 创建vector<ll> leaves。
   • 再次遍历节点编号1 ∼ n 1 \sim n1∼n，若outDeg[i] == 0，则将i ii加入leaves。
   • 由于遍历顺序是从小到大，leaves中元素天然升序，无需额外排序（代码中sort是冗余但无害的）。
4. 输出叶子：
   • 按顺序输出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;}