题解 | #连通块#

思路：

题目的主要信息：

n个房间，n-1条通道连通，这就是一棵树
树每个节点值记录在x数组
去掉树的一些边，使之成为k个子树，且每个子树的节点值和大于等于m，问可行性

方法一：dfs
具体做法：
主体思路是，将树分成每个部分刚好大于等于m，看是否有大于等于k个子树。
首先构建图，利用深度优先搜索自底向上将每个子树的节点值往上累加，每次遇到累加和大于等于m时，往上加的就归零，相当于切断该子树往上的边，同时计数k减一，最后检查k是否小于等于0即可。

class Solution {
public:
    //深度优先搜索函数相加和大于等于m即k减一
    int dfs(vector<vector<int>>& G, vector<int>& x, int n, int& k, int m, int u, int pre){
        if(k <= 0) //达成目标
            return 0;
        int sum = x[u - 1]; //节点值相加和
        for(int i = 0; i < G[u].size(); i++) //对相邻的每个节点深度优先搜索
            if(G[u][i] != pre)
                sum += dfs(G, x, n, k, m, G[u][i], u); 
        if(sum >= m){ //满足条件
            k--;
            return 0;
        }
        return sum;
    }
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < u.size(); i++){ //构建图
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        dfs(G, x, n, k, m, 1, -1); 
        return (k <= 0); 
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，dfs遍历树的每个节点
空间复杂度： $O(n)$ ，构建图的辅助数组G及递归栈深度

方法二：bfs
具体做法：
同样是方法一的思想，但是累加的和却用bfs实现。
我们利用degree数组记录每个节点的出度，因为我们构建的图是无向图，因此叶子节点出度为1，找到所有出度为1的点入队列，我们每次从叶子节点出发累加子树的节点值（类似方法一的自底向上加），即辅助数组y记录的是每个子树的累加节点和，一开始都为自己节点值。如果该子树节点和已经是大于等于m，我们可以像方法一一样，断掉该边，往旁边相连的都是加0，计数k减一；否则需要像旁边所有的辐射累加。
图片说明

class Solution {
public:
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        vector<vector<int> > G(n + 1);
        vector<int> degree(n + 1, 0);
        for(int i = 0; i < u.size(); i++){ //构建图
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
            degree[u[i]]++; //每个节点度数
            degree[v[i]]++;
        }
        vector<bool> vis(n + 1, false);
        queue<int> q;
        vector<int> y = x; //记录每棵子树的金币数
        for(int i = 0; i < n; i++){//所有度数为1的节点即叶子节点入队
            if(degree[i] == 1){
                q.push(i);
                vis[i] = true;
            }
        }
        while(!q.empty()){  //bfs
            int temp = q.front();
            q.pop();
            if(y[temp - 1] >= m){ //该子树数量大于m，计数并子树归零，代表截断
                k--;
                if(k <= 0) //够了满足条件
                    break;
                y[temp - 1] = 0;
            }
            for(int i = 0; i < G[temp].size(); i++){ //广度优先
                y[G[temp][i] - 1] += y[temp - 1]; //与该子树邻接的节点都要加上该子树的
                if(!vis[G[temp][i]]){
                    vis[G[temp][i]] = true;
                    q.push(G[temp][i]);
                }
            }
        }
        return k <= 0;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，多次遍历，最多也都是遍历树的每个节点
空间复杂度： $O(n)$ ，辅助队列、各个辅助数组的长度