C++ 120 ms, topological sort


  • 3
    I

    Based on
    https://leetcode.com/discuss/88737/sharing-my-c-solution-using-the-idea-of-topological-sort

     vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
         vector<int> ans;
         if(!n)
            return ans;
         if(n == 1)
         {
             ans.push_back(0);
             return ans;
         }
         vector<unordered_set<int>> v(n);
         for(int i = 0; i < edges.size();++i)
         {
            v[edges[i].first].insert(edges[i].second);
            v[edges[i].second].insert(edges[i].first);
         }
         vector<int> leaves;
         for(int i = 0; i < n; ++i)
            if(v[i].size() == 1)
               leaves.push_back(i);
         while(true)
         {
             vector<int> newleaves;
             for(int l : leaves)
             {
                  for(int i : v[l])
                  {
                      v[i].erase(l);
                      if(v[i].size() == 1)
                         newleaves.push_back(i);
                  }
             }
             if(newleaves.size() == 0)
                return leaves;
             leaves = newleaves;
         }
     }
    

Log in to reply
 

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