题解 | #连通块#

题目关键信息：
有n个结点，总共有n-1条边，第i个结点的金币数为 $图片说明$ ,现在要求把n个结点分割成K个连通区域，且每个连通区域的金币之和需要大于等于m
方法一：dfs

用二维数组list存储每个结点和它的相邻结点，visit数组记录结点是否被访问过,res记录分割次数
从根结点开始搜索，遇到访问过的结点直接跳过，未访问过的结点继续搜索，记录当前结点和它相邻结点的金币数，如果金币数大于等于m则分割次数增加，sum置0,为下一次统计连通区域的金币数做准备，返回sum(未达到m时则sum会继续累加直到达到m再分割)
遍历完所有结点后,分割次数大于等于k则可行，否则不可行

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param m int整型 
     * @param u int整型一维数组 
     * @param v int整型一维数组 
     * @param x int整型一维数组 
     * @return bool布尔型
     */
    ArrayList<Integer>[]list;
    boolean[]visit;
    ArrayList<Integer>child;
    int res;//统计分割次数
    public boolean solve (int n, int k, int m, int[] u, int[] v, int[] x) {
        // write code here
        list=new ArrayList[n+1];
        child=new ArrayList<>();
        for(int i=1;i<n+1;i++){
            list[i]=new ArrayList<Integer>(n);
        }
        for(int i=0;i<u.length;i++){
            list[u[i]].add(v[i]);
            list[v[i]].add(u[i]);//建图
        }
        visit=new boolean[n+1];//记录结点是否被访问过，避免同个结点被访问多次导致死循环
        dfs(x,k,m,1);//从第一个结点开始搜索
        return res>=k;//分割次数大于等于k则可行
    }
   int dfs(int[]x,int k,int m,int curr){
       int sum=x[curr-1];//记录当前结点的金币数
       for(int c:list[curr]){//访问当前结点的邻接结点
           if(visit[c])continue;//如果结点被访问过则直接跳过
           visit[c]=true;//标记被访问过的结点为true
           sum+=dfs(x,k,m,c);//统计当前结点和它连通结点的金币数
       }
       if(sum>=m){
           sum=0;//如果金币数超过m,sum置为0,不影响下一个连通区域的金币统计
           res++;;//分割次数增加
       }
       return sum;
   }
}

复杂度：
时间复杂度：深度优先搜索每个结点至少访问一次, $O(n)$
空间复杂度：递归栈大小不超过n,二维数组list的大小不超过 $n^{2}$ , $图片说明$
方法二：bfs

从叶子结点向上搜索，因此需要记录下所有结点的度数，因为是无向图，叶子结点的度数为1，所以找到所有度数为1的结点
将所有叶子结点入队，并且设置为已访问，避免后面访问结点的邻接结点时重复访问叶子结点
需要统计每个结点扩散出去后连通区域金钱数，为了方便记录，将x数组拷贝一份到money数组，从叶子结点开始搜素其邻接结点，记录金钱数到monney数组对应的位置，并且将未访问过的结点设置为已访问并入队
如果出队结点的金钱数已经超过m，说明已找到一个符合条件的连通区域，分割次数res增加,最后分割次数大于等于k，则返回true

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param m int整型 
     * @param u int整型一维数组 
     * @param v int整型一维数组 
     * @param x int整型一维数组 
     * @return bool布尔型
     */
    ArrayList<Integer>[]list;
    boolean[]visit;
    int[]degree;
    int res=0;//统计分割次数
    public boolean solve (int n, int k, int m, int[] u, int[] v, int[] x) {
        // write code here
        list=new ArrayList[n+1];
        degree=new int[n+1];
        for(int i=1;i<n+1;i++){
            list[i]=new ArrayList<Integer>(n);
        }
        for(int i=0;i<u.length;i++){
            list[u[i]].add(v[i]);
            list[v[i]].add(u[i]);//建图
            degree[u[i]]++;//统计各个结点的度数
            degree[v[i]]++;

        }
        visit=new boolean[n+1];//记录结点是否被访问过，避免同个结点被访问多次导致死循环
        return bfs(x,k,m);
    }
   boolean bfs(int[]x,int k,int m){
       Queue<Integer>q=new LinkedList<Integer>();
       int[]money=new int[x.length];
       System.arraycopy(x,0,money,0,x.length);//money数组记录每个结点和周围连通域的金钱值
       for(int i=1;i<degree.length;i++){
           if(degree[i]==1)
           {  q.offer(i);
               visit[i]=true;//将度数为1的叶子结点入队，并且设置为已访问，后面才不会重复入队
           }
       }
       //从叶子结点向上搜索其相邻结点
       while(!q.isEmpty()){
           int node=q.poll();
           if(money[node-1]>=m){
               res++;
               money[node-1]=0;//为下一个连通域做准备
           }
           for(int c:list[node]){
               money[c-1]+=money[node-1];//保存每个结点和周围连通域的金钱值
               if(!visit[c]){
                   visit[c]=true;
                   q.offer(c);//没有访问过的结点才入队，避免重复访问
               }
           }
       }return res>=k;//分割次数大于等于k则可行
   }
}

复杂度：
时间复杂度： $O(n)$ ,bfs至少访问每个结点一次
空间复杂度： $图片说明$ ,二维数组list的大小不超过 $n^{2}$ ，