Tags: tree topological-sort bfs
310. Minimum Height Trees, topological sorting, medium
explanation at gardner and tree
instead of whole array we just want the last level.
therefore erasing whole vector every time.
Code
```cpp
class Solution {
public:
vector findMinHeightTrees(int n, vector<vector>& edges) {
if (n == 1) return {0};
vector<vector> tree(n + 1);
vector indegree(n + 1, 0);
for (const auto& i: edges) {
int a = i[0], b = i[1];
tree[a].push_back(b);
tree[b].push_back(a);
indegree[a] ++;
indegree[b] ++;
}
queue qu;
for (int i = 0; i < indegree.size(); i++) {
if (indegree[i] == 1) {
qu.push(i);
}
}
vector topo;
while (!qu.empty()) {
int current_size = qu.size();
topo.clear();
for (int i = 0; i < current_size; i++) {
auto u = qu.front();
qu.pop();
topo.push_back(u);
for (const auto& v: tree[u]) {
if (--indegree[v] == 1) {
qu.push(v);
}
}
}
}
return topo;
}
};
```
</details>