leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0310.cpp (917B)

      1 class Solution {
      2   public:
      3     vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
      4         if (n == 0) return {};
      5         if (n == 1) return {0};
      6         if (n == 2) return {0, 1};
      7 
      8         vector<set<int>> adj(n);
      9         vector<int> count(n);
     10 
     11         for (auto &e : edges) {
     12             adj[e[0]].insert(e[1]);
     13             adj[e[1]].insert(e[0]);
     14             count[e[0]]++;
     15             count[e[1]]++;
     16         }
     17 
     18         queue<int> q;
     19         for (int i = 0; i < n; i++)
     20             if (count[i] == 1) q.push(i);
     21 
     22         vector<int> res;
     23         while (!q.empty()) {
     24             res.clear();
     25             for (int k = q.size(); k > 0; k--) {
     26                 int c = q.front();
     27                 q.pop();
     28                 res.push_back(c);
     29                 for (int n : adj[c]) {
     30                     if (--count[n] == 1) q.push(n);
     31                 }
     32             }
     33         }
     34 
     35         return res;
     36     }
     37 };