leetcode

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 };