// Minimum Height Trees #define REP(i, n) for (int i = 0; i < (n); i++) class Solution { public: vector findMinHeightTrees(int n, vector>& edges) { vector> es(n); vector d(n, 0); vector removed(n, false); for (auto &e: edges) { es[e.first].push_back(e.second); es[e.second].push_back(e.first); d[e.first]++; d[e.second]++; } vector leaves; REP(i, n) if (d[i] <= 1) leaves.push_back(i); while (n > 2) { vector leaves2; n -= leaves.size(); for (int u: leaves) { int p = -1; for (int v: es[u]) if (! removed[v]) p = v; removed[u] = true; if (--d[p] == 1) leaves2.push_back(p); } leaves.swap(leaves2); } return leaves; } }; /// find a diameter class Solution { vector> es; vector parent; int bfs(int u) { queue q; int last = u; fill(parent.begin(), parent.end(), -1); parent[u] = -2; q.push(u); while (! q.empty()) { u = q.front(); q.pop(); last = u; for (int v: es[u]) if (parent[v] == -1) { parent[v] = u; q.push(v); } } return last; } public: vector findMinHeightTrees(int n, vector>& edges) { es.resize(n); parent.resize(n); for (auto &e: edges) { es[e.first].push_back(e.second); es[e.second].push_back(e.first); } vector ancestors; for (int v = bfs(bfs(0)); v != -2; v = parent[v]) ancestors.push_back(v); vector ret{ancestors[ancestors.size()/2]}; if (ancestors.size() % 2 == 0) ret.push_back(ancestors[ancestors.size()/2-1]); return ret; } };