将节点分成尽可能多的组

标签: 广度优先搜索 并查集 图

难度: Hard

给你一个正整数 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 <= 104
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • ai != bi
  • 两个点之间至多只有一条边。

Submission

运行时间: 552 ms

内存: 18.7 MB

class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x - 1].append(y - 1)
            g[y - 1].append(x - 1)
        
        def bfs(start: int) -> int:  # 返回从 start 出发的最大深度
            time = [False] * n
            depth = 0
            time[start] = True
            q = [start]
            while q:
                tmp = q
                q = []
                for x in tmp:
                    for y in g[x]:
                        if not time[y]:
                            time[y] = True
                            q.append(y)
                depth += 1
            return depth

        color = [0] * n
        def is_bipartite(x: int, c: int) -> bool:  # 二分图判定，原理见视频讲解            
            color[x] = c
            for y in g[x]:
                if color[y] == -c:
                    continue
                if color[y] != 0:
                    return False
                if not is_bipartite(y, -c):
                    return False
            return True

        clock = 0
        for i, c in enumerate(color):
            if c: continue
            clock += 1
            if not is_bipartite(i, clock): return -1  # 如果不是二分图（有奇环），则无法分组
            # 否则一定可以分组
        value = [0] * clock
        for i, c in enumerate(color):
            if c == 0: continue
            value[abs(c)-1] = max(value[abs(c)-1], bfs(i))  # 枚举连通块的每个点，作为起点 BFS，求最大深度
        return sum(value)

Explain

该题解通过将问题转化为二分图检测来解决。步骤如下： 1. 构建图的邻接列表。 2. 使用颜色数组 `color` 来检测图是否为二分图。二分图可以被分成两组，其中任何一条边的两个顶点都属于不同的组。 3. 为每个未染色的节点尝试进行二分图染色，使用深度优先搜索（DFS）。如果发现某个节点及其相邻节点颜色相同，说明存在奇数环，返回-1。 4. 对每个连通分量使用广度优先搜索（BFS）来确定其深度，深度决定了可以分的组数。 5. 计算所有连通分量的深度和作为最终结果。

时间复杂度: O(V+E)

空间复杂度: O(V+E)

class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x - 1].append(y - 1)
            g[y - 1].append(x - 1)
        
        def bfs(start: int) -> int:
            time = [False] * n
            depth = 0
            time[start] = True
            q = [start]
            while q:
                tmp = q
                q = []
                for x in tmp:
                    for y in g[x]:
                        if not time[y]:
                            time[y] = True
                            q.append(y)
                depth += 1
            return depth

        color = [0] * n
        def is_bipartite(x: int, c: int) -> bool:
            color[x] = c
            for y in g[x]:
                if color[y] == -c:
                    continue
                if color[y] != 0:
                    return False
                if not is_bipartite(y, -c):
                    return False
            return True

        clock = 0
        for i, c in enumerate(color):
            if c: continue
            clock += 1
            if not is_bipartite(i, clock): return -1
        value = [0] * clock
        for i, c in enumerate(color):
            if c == 0: continue
            value[abs(c)-1] = max(value[abs(c)-1], bfs(i))
        return sum(value)

Explore

在二分图中，图的顶点可以分成两组，使得每组内的任何两个顶点之间都不存在边。使用颜色数组和正负号是为了方便地检测和标记这两组。具体来说，我们可以将一组顶点标记为+1，另一组标记为-1。当我们在图中遍历时，如果遇到一个已经标记的顶点，我们会检查它是否与当前节点颜色相反。如果相同，则表示图中存在同组的相邻节点，从而不满足二分图的条件。使用正负号的方法简化了这一检测过程，使得我们只需要一次比较即可确定是否违反了二分图的性质。

是的，当我们在进行二分图染色过程中发现一个节点与其相邻节点颜色相同时，这意味着我们无法将这两个相邻节点放在两个不同的组中，因此图中至少存在一个奇数长度的环。在二分图中，任何环的长度都应该是偶数，因为顶点应该交替出现在两个不同的组中。发现奇数环是判断一个图不是二分图的充分条件。因此，一旦检测到这种情况，就可以直接返回-1，表示图不是二分图。

在使用广度优先搜索（BFS）遍历图的过程中，需要确保每个节点仅被访问一次，这样可以避免重复计算和无限循环。`time`数组用来跟踪每个节点的访问状态。当开始访问一个节点时，我们将其在`time`数组中的对应值标记为`True`，表示该节点已被访问。这样，当我们遇到一个已标记的节点时，就知道不需要再次将其加入到队列中。使用这种方法，我们可以正确地计算出从每个起始节点开始的BFS的深度，从而确定每个连通分量的最大深度。