Today’s problem

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

Intuition

The key of this question is $|y - x| = 1$. We know that for a step further, the parity must change. Therefore, when we encounter a case when the parity has a problem (for example, a loop with three nodes and three edges), we would return -1. Otherwise, all we can do is to iterate the starting point of the graph to find which point is the best starting point.

Therefore, we can have our approach:

  1. We can use a dfs to find whether there is a parity issue or not.
  2. We can use a bfs to find the starting point.

Questions: why using bfs to find the starting point?

This is because we need to add a point to the next group if it has an edge connecting the current point and the next point.

Approach

  1. We can use a dfs to find whether there is a parity issue or not.
  2. We can use a bfs to find the starting point.

Complexity

  • Time complexity: $O(N^2)$

  • Space complexity: $O(N^2)$

Code

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