Problem

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] = [aᵢ, bᵢ] indicates that there is a bidirectional edge between nodes aᵢ and bᵢ. 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 [aᵢ, bᵢ], if aᵢ belongs to the group with index x, and bᵢ belongs to the group with index y, then |y - x| = 1.

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

https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/

Example 1:

case1

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⁴
  • edges[i].length == 2
  • 1 <= aᵢ, bᵢ <= n
  • aᵢ != bᵢ
  • There is at most one edge between any pair of vertices.

Test Cases

1
2
class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import pytest

from solution import Solution


@pytest.mark.parametrize('n, edges, expected', [
    (6, [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]], 4),
    (3, [[1,2],[2,3],[3,1]], -1),

    (
        26,
        [[9,16],[8,3],[20,21],[12,16],[14,3],[7,21],[22,3],[22,18],[11,16],[25,4],[2,4],[14,21],[23,3],[17,3],[2,16],[24,16],[13,4],[10,21],[7,4],[9,18],[14,18],[14,4],[14,16],[1,3],[25,18],[17,4],[1,16],[23,4],[2,21],[5,16],[24,18],[20,18],[19,16],[24,21],[9,3],[24,3],[19,18],[25,16],[19,21],[6,3],[26,18],[5,21],[20,16],[2,3],[10,18],[26,16],[8,4],[11,21],[23,16],[13,16],[25,3],[7,18],[19,3],[20,4],[26,3],[23,18],[15,18],[17,18],[10,16],[26,21],[23,21],[7,16],[8,18],[10,4],[24,4],[7,3],[11,18],[9,4],[26,4],[13,21],[22,16],[22,21],[20,3],[6,18],[9,21],[10,3],[22,4],[1,18],[25,21],[11,4],[1,21],[15,3],[1,4],[15,16],[2,18],[13,3],[8,21],[13,18],[11,3],[15,21],[8,16],[17,16],[15,4],[12,3],[6,4],[17,21],[5,18],[6,16],[6,21],[12,4],[19,4],[5,3],[12,21],[5,4]],
        4
    ),
    (
        92,
        [[67,29],[13,29],[77,29],[36,29],[82,29],[54,29],[57,29],[53,29],[68,29],[26,29],[21,29],[46,29],[41,29],[45,29],[56,29],[88,29],[2,29],[7,29],[5,29],[16,29],[37,29],[50,29],[79,29],[91,29],[48,29],[87,29],[25,29],[80,29],[71,29],[9,29],[78,29],[33,29],[4,29],[44,29],[72,29],[65,29],[61,29]],
        57
    ),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, n, edges, expected):
    assert sol.magnificentSets(n, edges) == expected

Thoughts

首先只有二部图才能进行这样的分组。二部图的判定在 785. Is Graph Bipartite? 中做了（支持非连通图），可以搬过来用。

如果整张图可以划分为几个各不相连的子图，那么求出每个子图的最大分组数量，总和就是题目的答案。

对于一个连通子图，只要计算出其直径（the length of the longest path between any two nodes in the graph），显然按照直径所在的路径排出来的分组数一定是最多的，数量等于图的直径加一。

开始直接搬 3203. Find Minimum Diameter After Merging Two Trees 里面计算直径的逻辑，结果不对。那里的快速计算方法只适用于树，在有环的情况下不一定能计算正确。

比如下图，如果初始节点是 v，第一次 DFS 会找到 u，再从 u 出发得到的「直径」是 3。但此图的直径其实是 4。

bad-diameter-case

（图片出自 https://cs.stackexchange.com/a/213）

只能是按广度优先搜索（BFS），计算出从每一个节点出发能得到的最大路径长度，取最大值则为直径。

在做 BFS 的时候，因为要计算出最大的路径长度（深度），可以像层序遍历树/二叉树那样，直接一层一层地处理（如 515. Find Largest Value in Each Tree Row），更直接地跟踪深度。

另外在计算连通子图的直径的时候，对子图中的所有节点都标记上「已处理」，这样直接在外层对所有顶点做一次扫描，就可以确保所有子图都处理一次且仅一次（不用像 721. Accounts Merge 那样先弄一个 disjoint set，再把每个子图筛出来）。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from collections import deque


class Solution:
    def magnificentSets(self, n: int, edges: list[list[int]]) -> int:
        max2 = lambda a, b: a if a >= b else b
        graph: list[list[int]] = [[] for _ in range(n)]
        for u, v in edges:
            graph[u-1].append(v-1)
            graph[v-1].append(u-1)

        # Checks if the graph is bipartite.
        colors = [-1] * n
        for u in range(n):
            if colors[u] >= 0: continue
            colors[u] = 0
            stack = [u]
            while stack:
                u = stack.pop()
                cu = colors[u]
                cv = 1 - cu
                for v in graph[u]:
                    if colors[v] == -1:
                        colors[v] = cv
                        stack.append(v)
                    elif colors[v] == cu:
                        return -1

        def bfs_depth(u: int) -> int:
            """Returns the max (0-indexed) depth starting from `u`."""
            visited = [False] * n
            visited[u] = True
            queue = deque([u])
            depth = -1
            while queue:
                depth += 1
                for _ in range(len(queue)): # Process the whole layer together. All these nodes have the same depth.
                    u = queue.popleft()
                    for v in graph[u]:
                        if not visited[v]:
                            visited[v] = True
                            queue.append(v)

            return depth

        def diameter(u: int) -> int:
            """Returns the diameter of sub-graph contains `u`.
            Which is the max bfs-depth starting from every node of the sub-graph."""
            finished[u] = True
            stack = [u]
            d = 0
            while stack:
                u = stack.pop()
                d = max2(d, bfs_depth(u))
                for v in graph[u]:
                    if not finished[v]:
                        finished[v] = True
                        stack.append(v)

            return d

        group_cnt = 0
        finished = [False] * n
        for u in range(n):
            if finished[u]: continue
            group_cnt += diameter(u) + 1

        return group_cnt
hard
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~