AcWing 1254. 找树根和孩子
原题链接
简单
作者:
王小强
,
2021-02-13 17:13:02
,
所有人可见
,
阅读 477
做简单题熟练多了!(重拳出击
)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
vector<vector<int>> g(N); // adjacency list
vector<int> nodes, indegrees(N);
int n, m, u, v;
int main(void) {
cin >> n >> m;
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
++indegrees[v];
nodes.emplace_back(u);
nodes.emplace_back(v);
}
// 入度为0的节点就是根节点
int root = -1, max = -1, max_child_size = -1;
for (const auto& node : nodes) {
if (!indegrees[node]) root = node;
int child_size = g[node].size();
if (child_size > max_child_size) {
max = node;
max_child_size = child_size;
}
}
sort(begin(g[max]), end(g[max]));
printf("%d\n", root);
printf("%d\n", max);
for (const auto& x : g[max]) printf("%d ", x);
}