Sharing my C++ solution using the idea of topological sort


  • 3
    T
    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if(n==1)
                return vector<int>(1, 0);
                
            vector<unordered_set<int>> myConnections(n);
            int N = edges.size(), i;
            int first, second;
            for(i=0; i<N; i++)
            {
                first = edges[i].first;
                second = edges[i].second;
                myConnections[first].insert(second);
                myConnections[second].insert(first);
            }
            
            vector<int> current;
            for(i=0; i<n; i++)
                if(myConnections[i].size()==1)
                    current.push_back(i);
                    
            while(true)
            {
                vector<int> next;
                for(int iCurrent : current)
                    for(int iNext : myConnections[iCurrent])
                    {
                        if(myConnections[iNext].erase(iCurrent));
                        if(myConnections[iNext].size()==1)
                            next.push_back(iNext);
                    }
                    
                if(next.size()==0)
                    return current;
                else
                    current = next;
            }
        }
    };

Log in to reply
 

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