今日题目

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

解题思路

本题的关键在于条件 $|y - x| = 1$。 每走一步，奇偶性必然改变。因此，当我们遇到奇偶性出现矛盾的情况时（例如，一个包含三个节点和三条边的环），应返回 -1。 否则，我们只需枚举图的起始点，找出最优的起始节点即可。

因此，解题思路如下：

  1. 用 DFS 判断图中是否存在奇偶性冲突。
  2. 用 BFS 寻找最优起始点。

问题：为什么用 BFS 寻找起始点？

因为我们需要将与当前节点有边相连的节点加入下一个分组。

算法步骤

  1. 用 DFS 判断图中是否存在奇偶性冲突。
  2. 用 BFS 寻找最优起始点。

复杂度分析

  • 时间复杂度：$O(N^2)$

  • 空间复杂度：$O(N^2)$

代码

class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        vis = [0] * (n + 1)
        bvis = [0] * (n + 1)
        e = [[] for _ in range(n + 1)]

        for x,y in edges:
            e[x].append(y)
            e[y].append(x)

        ans = 0
        clock = 0

        def bfs(x):
            nonlocal clock
            clock += 1
            bvis[x] = clock
            q = deque([(x,1)])
            res = 1
            while(len(q) > 0):
                now, dis = q.popleft()
                res = max(res, dis)
                for to in e[now]:
                    if bvis[to] == clock:
                        continue
                    bvis[to] = clock
                    q.append((to, dis + 1))
                    
            return res

        cur = 0                    

        def dfs(x):
            nonlocal cur
            cur = max(cur, bfs(x))
            # print(cur)
            tmp = 0
            for to in e[x]:
                if vis[to] == 0:
                    if vis[x] == 0:
                        print("Warning!", x)
                    vis[to] = -vis[x]
                    tmp += dfs(to)
                else:
                    if vis[to] != -vis[x]:
                        return -1
            return tmp

        for i in range(1, n + 1):
            if vis[i] == 0:
                cur = 0
                vis[i] = 1
                if dfs(i) < 0:
                    return -1
                # print("out: ", cur)
                ans += cur
        
        # print(bfs(5))

        return ans