[LeetCode] 310. Minimum Height Trees

https://leetcode.com/problems/minimum-height-trees/

Solution:
Based on the properties of the undirected graph, there will most two MHTs. (For example, only two elements (should be two), or three elements (one or two), ... But the rigorous proving is not available now...)). 

First step to build a graph to connect all the nodes. Usually one two-dimensional vector is ok for building a graph, but for this question, we will visit (or delete) some elements, so it will be convenient using unordered_set instead of vector. After building the graph, we can start the search by putting vertices with outdegree of 1 into a queue. Then loop the queue, for each element, find all the elements connected. Then for all the connected elements, reduce their outdegrees (-1) by removing the element initially found in the queue.  If their outdegree becomes 1, put them into the queue. Continue this loop until the number of the total number of the elements is less than 3. It is like a "bottom up" fashion to find the top elements or "roots". 

Code:

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if(n==1) return{0};
        vector<int> res;
        vector<unordered_set<int>> graph(n);
        queue<int> q;
        for(auto a:edges){
            graph[a.first].insert(a.second);
            graph[a.second].insert(a.first);
        }
        for(int i=0; i<n; ++i){
            if(graph[i].size() == 1) q.push(i); 
        }
        while(n>2){
            int l = q.size();
            n -= l;
            for(int i=0; i<l; ++i){
                int p = q.front();
                q.pop();
                for(auto a:graph[p]){
                    graph[a].erase(p);
                    if(graph[a].size() == 1) q.push(a);
                }
            }
        }
        while(q.size()){
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }
}; 

http://www.cnblogs.com/grandyang/p/5000291.html