BFS solution similar to topological-sort


  • 0
    L

    We can use an idea that is very similar to topological sort. Start with all leaf nodes, and then traverse level by level. In each iteration, remove current leaf nodes, update the graph, and add new leaf nodes. Note that when adding new leaf nodes to queue, we need to check if it's already in the queue. The algorithm stops when there is only one node in queue or there are only two nodes and they are adjacent.

    class Graph {
    public:
        bool if_directed;
        int v_num;
        vector<unordered_map<int,int>> dis;
        Graph(bool if_directed, int v_num, vector<pair<int, int>> &edges) {
            vector<vector<int>> e(edges.size(),vector<int>(3,0));
            for(int i=0;i<edges.size();i++) {
                e[i][0]=edges[i].first;
                e[i][1]=edges[i].second;
                e[i][2]=1;
            }
            to_graph(if_directed,v_num,e);
        }
        Graph(bool if_directed, int v_num, vector<vector<int>> &e) {
            to_graph(if_directed,v_num,e);
        }
        bool is_adjacent(int a, int b) {
            return dis[a].find(b)!=dis[a].end();
        }
        void to_graph(bool if_directed, int v_num, vector<vector<int>> &e) {
            this->if_directed=if_directed;
            this->v_num=v_num;
            dis.assign(v_num,unordered_map<int,int>());
            for(int i=0;i<e.size();i++) {
                int a=e[i][0],b=e[i][1],c=e[i][2];
                if (dis[a].find(b)==dis[a].end()) {
                    dis[a][b]=c;
                } else {
                    dis[a][b]=min(dis[a][b],c);
                }
                if (!if_directed) {
                    if (dis[b].find(a)==dis[b].end()) {
                        dis[b][a]=c;
                    } else {
                        dis[b][a]=min(dis[b][a],c);
                    }
                }
            }
        }
    };
    
    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<int> res;
            Graph g(false,n,edges);
            queue<int> q;
            int count;
            for(int i=0;i<n;i++) {
                if (g.dis[i].size()==1) {
                    int next=g.dis[i].begin()->first;
                    q.push(i);
                } else if (g.dis[i].size()==0) {
                    q.push(i);
                }
            }
            count=q.size();
            while (!q.empty()) {
                if ( q.size()==1 || ( q.size()==2 && ( q.front()==q.back() || g.is_adjacent(q.front(),q.back()) ) ) )
                    break;
                int new_count=0;
                unordered_set<int> exist;
                for(int i=0;i<count;i++) {
                    int cur=q.front();
                    q.pop();
                    queue<int> p;
                    for(unordered_map<int,int>::const_iterator it=g.dis[cur].begin();it!=g.dis[cur].end();it++)
                        p.push(it->first);
                    while (!p.empty()) {
                        int next=p.front();
                        p.pop();
                        g.dis[cur].erase(next);
                        g.dis[next].erase(cur);
                        if (g.dis[next].size()==1 && exist.find(next)==exist.end()) {
                            q.push(next);
                            exist.insert(next);
                            new_count++;
                        }
                    }
                }
                count=new_count;
            }
            while(!q.empty()) {
                res.push_back(q.front());
                q.pop();
            }
            return res;
        }
    };
    

Log in to reply
 

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