2493. 将节点分成尽可能多的组

🔴 🔖 广度优先搜索 并查集 图 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.

You are also given a 2D integer array edges, where edges[i] = [ai, bi] indicates that there is a bidirectional edge between nodes ai and bi. Notice that the given graph may be disconnected.

Divide the nodes of the graph into m groups (1-indexed) such that:

Each node in the graph belongs to exactly one group.
For every pair of nodes in the graph that are connected by an edge [ai, bi], if ai belongs to the group with index x, and bi belongs to the group with index y, then |y - x| = 1.

Return the maximum number of groups (i.e., maximumm ) into which you can divide the nodes. Return -1 if it is impossible to group the nodes with the given conditions.

Example 1:

Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
Output: 4
Explanation: As shown in the image we:
Add node 5 to the first group.
Add node 1 to the second group.
Add nodes 2 and 4 to the third group.
Add nodes 3 and 6 to the fourth group.
We can see that every edge is satisfied.
It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.

Example 2:

Input: n = 3, edges = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied.
It can be shown that no grouping is possible.

Constraints:

1 <= n <= 500
1 <= edges.length <= 10^4
edges[i].length == 2
1 <= ai, bi <= n
ai != bi
There is at most one edge between any pair of vertices.

题目大意

给你一个正整数 n ，表示一个无向图中的节点数目，节点编号从 1 到 n 。

同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条双向边。注意给定的图可能是不连通的。

请你将图划分为 m 个组（编号从 1 开始），满足以下要求：

图中每个节点都只属于一个组。
图中每条边连接的两个点 [ai, bi] ，如果 ai 属于编号为 x 的组，bi 属于编号为 y 的组，那么 |y - x| = 1 。

请你返回最多可以将节点分为多少个组（也就是最大的 m ）。如果没办法在给定条件下分组，请你返回 -1 。

示例 1：

输入： n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
输出： 4
解释： 如上图所示，
节点 5 在第一个组。
节点 1 在第二个组。
节点 2 和节点 4 在第三个组。
节点 3 和节点 6 在第四个组。
所有边都满足题目要求。
如果我们创建第五个组，将第三个组或者第四个组中任何一个节点放到第五个组，至少有一条边连接的两个节点所属的组编号不符合题目要求。

示例 2：

输入： n = 3, edges = [[1,2],[2,3],[3,1]]
输出： -1
解释： 如果我们将节点 1 放入第一个组，节点 2 放入第二个组，节点 3 放入第三个组，前两条边满足题目要求，但第三条边不满足题目要求。
没有任何符合题目要求的分组方式。

提示：

1 <= n <= 500
1 <= edges.length <= 10^4
edges[i].length == 2
1 <= ai, bi <= n
ai != bi
两个点之间至多只有一条边。

解题思路

构建邻接表：
使用邻接表存储图结构，方便快速遍历邻居节点。
BFS 检测奇环：
- 使用 BFS 遍历每个连通分量，记录节点到根节点的深度。
- 如果遍历过程中发现 相邻节点深度之差为奇数，说明存在奇数环，不符合要求，直接返回 -1。
计算最大组数：
- 对于每个连通分量，选取不同的起点进行 BFS，记录最大深度。
- 连通分量的最大深度即为当前分量的组数，累加到结果中。
返回结果：
输出所有连通分量的最大可能分组数量。

复杂度分析

时间复杂度：O(n + m)，其中 n 为节点数，m 为边数。构建邻接表 + 遍历所有连通分量 + BFS 检查节点。
空间复杂度：O(n + m)，存储邻接表、访问标记和节点深度。

代码

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var magnificentSets = function (n, edges) {
	// 构建邻接表
	const graph = Array.from({ length: n + 1 }, () => []);
	for (const [u, v] of edges) {
		graph[u].push(v);
		graph[v].push(u);
	}

	const visited = Array(n + 1).fill(false);
	let maxGroups = 0;

	// BFS 检查是否有奇环，同时计算深度
	const bfs = (start) => {
		const queue = [[start, 1]];
		const nodeDepths = new Map();
		let maxDepth = 1;

		while (queue.length) {
			const [node, depth] = queue.shift();
			if (nodeDepths.has(node)) {
				if ((nodeDepths.get(node) - depth) % 2 !== 0) return -1; // 奇环
				continue;
			}
			nodeDepths.set(node, depth);
			maxDepth = Math.max(maxDepth, depth);

			for (const neighbor of graph[node]) {
				if (!nodeDepths.has(neighbor)) {
					queue.push([neighbor, depth + 1]);
				}
			}
		}
		return maxDepth;
	};

	// 遍历所有连通分量
	for (let i = 1; i <= n; i++) {
		if (!visited[i]) {
			const componentNodes = [];
			const queue = [i];
			visited[i] = true;

			// 获取连通分量中的所有节点
			while (queue.length) {
				const node = queue.shift();
				componentNodes.push(node);
				for (const neighbor of graph[node]) {
					if (!visited[neighbor]) {
						visited[neighbor] = true;
						queue.push(neighbor);
					}
				}
			}

			let bestDepth = 0;
			for (const node of componentNodes) {
				const depth = bfs(node);
				if (depth === -1) return -1;
				bestDepth = Math.max(bestDepth, depth);
			}
			maxGroups += bestDepth;
		}
	}

	return maxGroups;
};

题号	标题	题解	标签	难度	力扣
102	二叉树的层序遍历	[✓]	`树` `广度优先搜索` `二叉树`	🟠	🀄️open in new window 🔗open in new window
785	判断二分图		`深度优先搜索` `广度优先搜索` `并查集` `1+`	🟠	🀄️open in new window 🔗open in new window
2608	图中的最短环		`广度优先搜索` `图`	🔴	🀄️open in new window 🔗open in new window

2493. 将节点分成尽可能多的组

# 2493. 将节点分成尽可能多的组

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2493. 将节点分成尽可能多的组

题目

题目大意

解题思路

复杂度分析

代码

相关题目