【深度优先搜索 图论 树】2872. 可以被 K 整除连通块的最大数目

本文涉及知识点

深度优先搜索 图论 树
图论知识汇总

LeetCode 2872. 可以被 K 整除连通块的最大数目

给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个下标从 0 开始长度为 n 的整数数组 values ，其中 values[i] 是第 i 个节点的 值 。再给你一个整数 k 。
你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个 连通块的值 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k 整除，那么我们说这是一个 合法分割 。
请你返回所有合法分割中，连通块数目的最大值 。
示例 1：

输入：n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
输出：2
解释：我们删除节点 1 和 2 之间的边。这是一个合法分割，因为：

• 节点 1 和 3 所在连通块的值为 values[1] + values[3] = 12 。
• 节点 0 ，2 和 4 所在连通块的值为 values[0] + values[2] + values[4] = 6 。
  最多可以得到 2 个连通块的合法分割。
  示例 2：

输入：n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3
输出：3
解释：我们删除节点 0 和 2 ，以及节点 0 和 1 之间的边。这是一个合法分割，因为：

• 节点 0 的连通块的值为 values[0] = 3 。
• 节点 2 ，5 和 6 所在连通块的值为 values[2] + values[5] + values[6] = 9 。
• 节点 1 ，3 和 4 的连通块的值为 values[1] + values[3] + values[4] = 6 。
  最多可以得到 3 个连通块的合法分割。

提示：

1 <= n <= 3 * 10⁴
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
values.length == n
0 <= values[i] <= 10⁹
1 <= k <= 10⁹
values 之和可以被 k 整除。
输入保证 edges 是一棵无向树。

深度优先搜索

共n-1条边，对应除根节点外，所有节点和其父节点。
除根节点外，子树所有节点之和如果是k的倍数，则断开。因为后代断开，不影响祖先节点断开。
连通块数 = 断开数 +1。

代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

class Solution {
public:
	int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
		m_values = values;
		m_iK = k;
		auto neiBo = CNeiBo::Two(n, edges, false);
		DFS(neiBo, 0, -1);
		return m_iRet+1;
	}
	long long DFS(vector<vector<int>>& neiBo, int cur, int par)
	{
		long long llSum = m_values[cur];
		for (const auto& next : neiBo[cur])
		{
			if (next == par)
			{
				continue;
			}
			llSum += DFS(neiBo, next, cur);
		}
		if ((0 == llSum % m_iK)&&( 0 != cur)) { m_iRet++; }
		return llSum;
	}
	vector<int> m_values;
	int m_iK;
	int m_iRet = 0;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。