leetcode 310. 最小高度树拓扑排序

偏执的太偏执、 2022-12-16 05:54 123阅读 0赞

**使用邻接矩阵会超时  
使用邻接表就不超时了**  
**每次去掉度为1的点  
到最后的两个以内的时候停止**

#define debug(x) cout<<#x<<": "<<(x) <<endl;
    
    class Solution { 
    public:
        vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { 
            if(n==1){ 
                return { 0};
            }
            vector< vector<int> > adj = vector<vector<int>>(n,vector<int>(0));
            vector<int> du(n,0);
            for(vector<int> one:edges){ 
                int a = one[0];
                int b = one[1];
                adj[a].push_back(b);
                adj[b].push_back(a);
                du[a]++;
                du[b]++;
            }
            
            vector<int> q;
            
            for(int i=0;i<n;i++){ 
                if(du[i]==1){ 
                    q.push_back(i);
                }
            }
            
            int nn = n;
            while(!q.empty()){ 
                
                if(nn<=2){ 
                    return q;
                }
                
                vector<int>qq;
                for(int j=0;j<q.size();j++){ 
                    int top = q[j];
                    du[top]--;
                    for(int i : adj[top]){ 
                        du[i] --;
                        if(du[i]==1){ 
                            qq.push_back(i);
                        }
                    }
                    nn--;
                }
                q = qq;
            }
            return q;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7cc5f181232242ad813c584744aacdf3.png