leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0310.cpp (917B)

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