题目
给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。
输入格式
第一行：n，m，表示树的节点数和边数。
以下m行：每行两个结点x和y，表示y是x的孩子。
输出格式
第一行：树根：root；
第二行：孩子最多的结点max；
第三行：max的孩子（按编号由小到大输出）。
数据范围
,
,
,
数据保证孩子最多的结点唯一。
输入样例1：
8 7
4 1
4 2
1 3
1 5
2 6
2 7
2 8
输出样例1：
4
2
6 7 8
输入样例2：
10 9
661 43
43 270
43 155
155 691
661 201
661 768
661 889
43 302
201 98
输出样例2：
661
661
43 201 768 889
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <iostream>
#include <unordered_set>
#include <queue>
#define N 1010
using namespace std;
struct Tree
{
int v, cnt;
priority_queue<int, vector<int>, greater<int>> child;
bool root = true;
}tree[N];
int n, m;
int main()
{
cin >> n >> m;
unordered_set<int> items;
Tree maxTree;
int count = -1;
for (int i = 0; i < m; ++ i)
{
int a, b;
cin >> a >> b;
items.insert(a);
tree[a].v = a;
tree[a].child.push(b);
tree[b].root = false;
++ tree[a].cnt;
if (tree[a].cnt > count)
{
count = tree[a].cnt;
maxTree = tree[a];
}
}
for (auto i: items)
if (tree[i].root)
{
cout << tree[i].v << endl;
break;
}
auto& t = maxTree;
cout << t.v << endl;
while (t.child.size())
{
cout << t.child.top() << " ";
t.child.pop();
}
cout << endl;
return 0;
}
|
