abc
unknown
c_cpp
3 years ago
1.4 kB
3
Indexable
// https://www.codingninjas.com/codestudio/library/find-the-roots-of-a-tree-that-gives-minimum-height
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> degree(n, 0);
vector<vector<int>> neighborVertex(n);
for (int i = 0; i < n - 1; ++ i) {
int x, y;
cin >> x >> y;
degree[x] ++;
degree[y] ++;
neighborVertex[x].push_back(y);
neighborVertex[y].push_back(x);
}
queue<int> q;
for (int idx = 0; idx < n; ++ idx) {
if (degree[idx] == 1) {
q.push(idx);
}
}
int temp = n;
while (temp > 2) {
temp = temp - q.size();
int tmp = q.size();
for (int i = 0; i < tmp; ++ i) {
int root = q.front();
q.pop();
for (int j = 0; j < neighborVertex[root].size(); ++j) {
degree[neighborVertex[root][j]] --;
if (degree[neighborVertex[root][j]] == 1) {
q.push(neighborVertex[root][j]);
}
}
}
}
vector<int> res;
while (!q.empty()) {
res.push_back(q.front());
q.pop();
}
sort(res.begin(), res.end());
for (auto i: res) {
cout << i << " ";
}
return 0;
}Editor is loading...