首页 > 其他 > 详细

最小高度树

时间:2021-08-11 18:57:49      阅读:27      评论:0      收藏:0      [点我收藏+]
技术分享图片

 

 

变量简洁正确完整思路
拓扑排序,删除前的图A是,删除入度为1的节点后的图B,A的最小生成树是B的最小生成树叶子接上删除的节点,
无向图拓扑排序,入度至少为1,初始化graph需要edges[i][0]  edges[i][1]都初始化为彼此,都要更新入度,topoSort把入度1都放入que,然后一次性删除掉que原来入度1的元素也就是叶子元素(indegrees[cur]=0表示cur删除),对邻接的indegrees[graph[cur][i]]大于1的
--如果是1就把graph[cur][i]放到que,这样
[image:1628663260701.png]
每次while(cnt--)可以删除掉所有叶子节点,用cnt表示此次需要删除的叶子节点
[image:1628663584807.png]
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n==1)return {0};
        if(n==2)return {0,1};
        indegrees.resize(n);
        graph.resize(n);
        for(int i=0;i<edges.size();i++){
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
            indegrees[edges[i][0]]++;
            indegrees[edges[i][1]]++;
        }
        return topoSort(n);
    }
private:
    vector<int>topoSort(int n){
        queue<int>que;
        for(int i=0;i<n;i++)if(indegrees[i]==1)que.push(i);
        int cnt=que.size();
        while(n>2){
            n-=cnt;
            while(cnt--){
                int cur=que.front();que.pop();
                indegrees[cur]=0;
                for(int i=0;i<graph[cur].size();i++){
                    if(indegrees[graph[cur][i]]>1){
                        indegrees[graph[cur][i]]--;
                        if(indegrees[graph[cur][i]]==1)que.push(graph[cur][i]);
                    }
                }
            }
            cnt=que.size();
        }
        vector<int>ans;
        while(!que.empty()){
            ans.push_back(que.front());
            que.pop();
        }
        return ans;
    }
    vector<vector<int>>graph;
    vector<int>indegrees;
};

 

最小高度树

原文:https://www.cnblogs.com/zhouzihong/p/15128096.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!