一本通-1336:【例3-1】找树根和孩子¶
【题目描述】 给定一棵树,输出树的根root,孩子最多的结点max以及他的孩子。
【输入】 第一行:n(结点个数≤100),m(边数≤200)。
以下m行:每行两个结点x和y,表示y是x的孩子(x,y≤1000)。
【输出】 第一行:树根:root; 第二行:孩子最多的结点max; 第三行:max的孩子(按编号由小到输出)。
【输入样例】 8 7 4 1 4 2 1 3 1 5 2 6 2 7 2 8
【输出样例】 4 2 6 7 8
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int> > grid(105);
vector<int> inDegree(105);
void solve()
{
int root = -1, node = -1, maxVal = 0;
for (int i = 1; i <= n; ++i) {
if (grid[i].size() > maxVal) {
maxVal = grid[i].size();
node = i;
}
if (inDegree[i] == 0) root = i;
}
cout << root << endl;
cout << node << endl;
int len = grid[node].size();
sort(grid[node].begin(), grid[node].end());
for (int i = 0; i < len; ++i) {
cout << grid[node][i];
if (i != len - 1) cout << ' ';
}
cout << endl;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
int from, to;
for (int i = 0; i < m; ++i) {
cin >> from >> to;
grid[from].push_back(to);
++inDegree[to];
}
solve();
return 0;
}