ROOT
264 字
1 分钟
ROOT
题目描述
你找不到,你的,手了
给定一棵包含 n 个节点的有根树,节点编号为 1 ~ n。输入以 n - 1 条有向边 (a_i, b_i) 表示:存在一条从 a_i 指向 b_i 的边,且整棵树构成一棵树。
请输出:
- 树的根节点编号(唯一,入度为 0);
- 所有叶子节点编号(出度为 0),按升序排列。
输入描述
第一行输入整数 n (1 <= n <= 10^5)。 接下来 n - 1 行,每行输入两个整数 a_i, b_i (1 <= a_i, b_i <= n),表示一条有向边 a_i -> b_i。
输出描述
第一行输出根节点编号。 第二行输出所有叶子节点编号(升序,空格分隔)。
示例1
输入
31 21 3输出
12 3备注
无
我的代码
#include <bits/stdc++.h>using namespace std;int main (){ int n; cin>>n; vector <int> a[n+1]; //入度 vector <int> b[n+1]; //出度 for(int i=1;i<n;i++) { int x; cin>>x; b[x].push_back(x); int y; cin>>y; a[y].push_back(y); } for(int i=1;i<=n;i++) sort(a[i].begin(),a[i].end()); for(int i=1;i<=n;i++) { if(a[i].size()==0) { cout<<i<<"\n"; break; } } for(int i=1;i<=n;i++) { if(b[i].size()==0) { cout<<i<<" ";
} }}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




