# My 88ms C++ TOPO-SORT solution with explanation,O(n+e) time and space.

• ``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<vector<int>> graph(n,vector<int>());
vector<int> degree(n),ret;
for(const auto & x:edges){/// build graph
degree[x.first]++;degree[x.second]++;
graph[x.first].push_back(x.second);
graph[x.second].push_back(x.first);
}
queue<int> que;que.push(-1);/// init queue with -1, -1 is a separator
for(int i = 0; i < n; i++)
if(degree[i] == 1)
que.push(i);
for(int i = 2; i < n; i++){/// There are 2 MHTs at most;
int now = que.front();que.pop();
if(now == -1)
que.push(-1),i--;/// push back the separator
else
for(const auto & x:graph[now])
if(--degree[x] == 1)
que.push(x);
}
while(que.front()!=-1) que.pop();
que.pop();/// pop out the separator, the rest is the result.
while(!que.empty())
ret.push_back(que.front()),que.pop();
return ret.size()?ret:vector<int>{0};
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.