Leetcode 310 Solution

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> res;
        if (edges.size() == 0)
        {
            res.push_back(0);
            return res;
        }

        vector<set<int>> neighbors;
        int left_nodes = n;
        for (int i = 0; i < n; i++)
            neighbors.push_back(set<int>());

        for (auto it = edges.begin(); it != edges.end(); it++)
        {
            neighbors[it->first].insert(it->second);
            neighbors[it->second].insert(it->first);
        }

        queue<int> q;

        for (int i = 0; i < n; i++)
        {
            if (neighbors[i].size() == 1)
                q.push(i);
        }

        while (left_nodes > 2)
        {
            int size = q.size();
            left_nodes -= size;

            for (int i = 0; i < size; i++)
            {
                int node1 = q.front();
                q.pop();

                int node2 = *neighbors[node1].begin();
                neighbors[node2].erase(node1);

                if (neighbors[node2].size() == 1)
                    q.push(node2);
            }
        }

        for (int i = 0; i < left_nodes; i++)
        {
            res.push_back(q.front());
            q.pop();
        }

        return res;
    }
};