abc
unknown
c_cpp
2 years ago
1.4 kB
2
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...