视频加载失败

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#

输入

3
1 2
1 3

输出

1
2 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<<" ";
}
}
}

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

ROOT
https://www.xiaobaibai454.top/posts/study-26-10-30-2/
作者
Xiao_baibai
发布于
2026-10-30
许可协议
CC BY-NC-SA 4.0

评论区

Profile Image of the Author
Xiao_baibai
你是怎么找到这里的???
分类
最新动态
站点统计
文章
25
分类
4
标签
5
总字数
17,871
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录