题解 | #连通块#

一.题目描述
NC572连通块
有一棵树有n个节点n-1条边，需要判断是否可以将这棵树划分为k个连通块并且每一个联通块的节点的总和是不是大于等于m。

二.算法(暴力搜索)
我们需要判断是否可以将这棵树划分成k个连通块并且每个连通块的总和是不是大于等于m，等价于是否可以把树划分成大于等于k个的连通块并且每一个连通块的节点总和大于等于m。那么我们就可以利用暴力对树形结构进行搜索，记录每一个连通块的节点总和，对于连通块的总和大于等于m对计数器进行加一操作，最后比较计数器的最后大小和m，要是计数器的大小大于m，最后的返回值就是true，否者返回值就是false。下面是完整代码:

class Solution {
public:
    vector<int>mp[200010];
    int s[200010],cnt=0;//s记录每一个连通块的节点和，cnt表示计数器的值
    //now表示当前节点
    //pre表示搜索的上一个节点 防止重复的搜索
    //m表示每个连通块需要大于的值
    //num表示每一个节点的值
    void dfs(int now,int pre,int m,vector<int>&num){
       s[now]=num[now-1];//记录点权
        for(auto i:mp[now]){
            if(i==pre){//重复搜索直接跳过
                continue;
            }
            dfs(i,now,m,num);
            s[now]+=s[i];
        }
        //要是连通块的值大于等于m 计数器加一
        if(s[now]>=m){
            s[now]=0;
            cnt++;
        }
    }
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        ///建图 
        for(int i=0;i<n-1;i++){
             mp[v[i]].push_back(u[i]);
             mp[u[i]].push_back(v[i]);
         }
        dfs(1,-1,m,x);
        //判断是否满足条件
        if(cnt>=k){
            return true;
        } else {
            return false;
        }
    }
};

时间复杂度：对每一个点进行了一次遍历
空间复杂度： 需要二维vector来建图
优缺点：代码实现的思路简单，并且代码也容易实现
三.算法(bfs)
(图片来自牛客)
对于算法二我们是从根节点从下至上的进行搜索，同样我们可以从叶末利用bfs进行搜索，思路和前面的算法大致相同，下面是完整代码和详细注释:

class Solution {
public:
/*
说是自下而上实际上是从末端进行分成连通块
*/
    vector<int>mp[200010];
    bool st[200010];
    int d[200010],cnt=0;
    //x表示点权
    //k,m分别表示之至少需要的连通块个数和每一个连通块的点权和要大于等于m
    bool bfs(vector<int> x,int k,int m,int n){
        queue<int>q;
        int w[200010];//对于每个连通块的值的记录
        for(int i=1;i<=n;i++){
            w[i]=x[i-1];
        }
        for(int i=1;i<=n;i++){
            if(d[i]==1){
                //找到叶的末端放入队列
                q.push(i);
                st[i]=true;
            }
        }
        while(q.size()){
            int top=q.front();
            q.pop();
            if(w[top]>=m){
                cnt++;
                w[top]=0;
            }
            for(int i:mp[top]){
                w[i]+=w[top];
                if(!st[i]){
                    st[i]=true;
                    q.push(i);
                }
            }
        }
        //是否大于等于k
        if(cnt>=k){
            return true;
        } else {
            return false;
        }
    }
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        for(int i=0;i<n-1;i++){
            mp[u[i]].push_back(v[i]);
            mp[v[i]].push_back(u[i]);
            //记录边权
            d[u[i]]++;
            d[v[i]]++;
        }
        return bfs(x,k,m,n);
    }
};

时间复杂度：对每一个点进行了一次遍历
空间复杂度： 需要二维vector来建图
优缺点：代码实现的思路简单，并且代码也容易实现