连通块

[编程题]连通块

热度指数：495 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有n个房间，房间之间有通道相连，一共有n-1个通道，每两个房间之间都可以通过通道互相到达。

第i个房间有 $x_i$ 个金币。

现在牛牛想通过封闭一些通道来把n个房间划分成k个互相不连通的区域，他希望这k个区域内部的金币数目和都大于等于m，你需要告诉他这是否可行。

示例1

输入

3,2,3,[1,1],[2,3],[1,3,2]

输出

true

说明

切断1和2之间的通道，划分出了2个金币数为3的连通块

备注:



第一个参数n代表房间数量
第二个参数k代表要划分成k块区域。
第三个参数m代表每块区域的金币数要大于等于m
第四、五个参数vector u,v代表通道，与通过通道相连
第六个参数vector x代表每个房间的金币数

算法知识视频讲解

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param n int整型 
   * @param k int整型 
   * @param m int整型 
   * @param u int整型vector 
   * @param v int整型vector 
   * @param x int整型vector 
   * @return bool布尔型
   */
  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 < n - 1; ++i)
      g[u[i]].emplace_back(v[i]);
    
    function<long(int)> dfs = [&](int curr) -> int {
      if (k <= 0) return 0;
      int total = x[curr - 1];
      for (const auto& child : g[curr])
        total += dfs(child);
      
      return total >= m ? --k, 0 : total;
    };
    
    dfs(1);
    return k <= 0;
  }
};

发表于 2021-07-28 19:14:19 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 连通块
     * @param n int整型 
     * @param k int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return bool布尔型
     */
    vector<int> G[200003];
    int DFS(int s, int n, int &k, int m, vector<int>& x){
        if(k<=0)
            return 0;
        int sum = x[s];
        for(auto &v: G[s])
            sum += DFS(v, n, k, m, x);
        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) {
        for(int i=0;i<n-1;i++)
            G[u[i]].push_back(v[i]);
        DFS(1, n, k, m, x);
        return k<=0;
    }
};

发表于 2020-07-24 03:08:38 回复(1)

Python 3

ZhongHaoWang

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @param k int整型 
# @param m int整型 
# @param u int整型一维数组 
# @param v int整型一维数组 
# @param x int整型一维数组 
# @return bool布尔型
#
import collections
class Solution:
    def solve(self , n , k , m , u , v , x ):
        # write code here
        
        edges = collections.defaultdict(list)
        for i in range(n - 1):
            edges[u[i]].append(v[i])
            edges[v[i]].append(u[i])
        
        def dfs(cur_node,visited):
            nonlocal k
            if k <= 0:
                return 0
            ans = x[cur_node - 1]
            for next_ in edges[cur_node]:
                if next_ not in visited:
                    visited.add(next_)
                    ans += dfs(next_,visited)
            if ans >= m:
                k -= 1
                return 0
            return ans
        
        dfs(1,{1})
        return k <= 0

发表于 2021-09-04 13:31:54 回复(0)

牛客745599318号

这是一棵树啊！！

class Solution {
public:
    /**
     * 连通块
     * @param n int整型 
     * @param k int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return bool布尔型
     */
	vector<int> g[200005];
	pair<int,int> dfs(int u, int father, int m, vector<int>& x){
		auto res = make_pair(0, x[u]);
		int sum = x[u];
		for(auto v : g[u]){
			if(v==father) continue;
			auto ret = dfs(v,u,m,x);
			res.first += ret.first;
			res.second += ret.second;
		}
		if(res.second >= m){
			res.first ++;
			res.second = 0;
		}
		return res;
	}
    bool solve(int n, int k, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        // write code here
		for(int i=0;i<u.size();i++){
			g[u[i]-1].push_back(v[i]-1);
			g[v[i]-1].push_back(u[i]-1);
		}
		return dfs(0,-1, m, x).first>=k;
    }
};

发表于 2020-07-24 09:32:34 回复(0)