描述 一棵树有n个结点,已知树上所有的父子结点关系,请问该树的根是几号结点,哪个结点的子结点最多,该结点有哪些子结点。 输入描述 第一行,有1个整数n代表结点数量(0<n≤100) 接下来若干行;每行两个结点x和y,表示y是x的孩子(1≤x,y≤1000) 请注意:树上结点的编号不一定是连续的 输出描述 第一行输出树根的编号。 第二行输出孩子最多的结点编号(如果有多个结点的子结点都是最多的,则输出编号最大的那个)。 第三行输出第二行求出的孩子最多的结点,有哪些孩子,按照编号从小到大,输出这些孩子的编号,用空格隔开。使用C++实现
时间: 2024-03-25 22:36:18 浏览: 91
我们第一行包括两个整数n,k(1<=n<=100,k<=6e5),表示有n个数字,目标和为k 第二行输入n个整数(c1 c2
下面是一份C++的代码供参考:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1000;
vector<int> g[MAXN];
bool vis[MAXN];
int degree[MAXN];
int main()
{
int n;
cin >> n;
// 读入树的边
for (int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
g[x].push_back(y);
degree[y]++;
}
// 找到根结点
int root = 1;
while (degree[root] > 0)
root++;
// BFS,找到孩子最多的结点
queue<int> q;
q.push(root);
vis[root] = true;
int max_child = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
max_child = max(max_child, (int)g[u].size());
for (int i = 0; i < g[u].size(); i++)
{
int v = g[u][i];
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
// 找到孩子最多的结点的编号
vector<int> max_nodes;
for (int i = 1; i <= n; i++)
if ((int)g[i].size() == max_child)
max_nodes.push_back(i);
int max_node = *max_element(max_nodes.begin(), max_nodes.end());
// 输出结果
cout << root << endl;
cout << max_node << endl;
sort(g[max_node].begin(), g[max_node].end());
for (int i = 0; i < g[max_node].size(); i++)
cout << g[max_node][i] << " ";
cout << endl;
return 0;
}
```
该代码首先读入树的边,然后通过计算每个结点的入度,找到根结点。接着通过BFS遍历树,找到孩子最多的结点。最后输出结果即可。
阅读全文