Divide Nodes Into the Maximum Number of Groups

lcpy gen -n 2493   # by problem number
lcpy gen -s divide_nodes_into_the_maximum_number_of_groups   # by problem name

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 if we create a fifth group and move any node from the third or fourth group to it, at least one of the edges will not be satisfied.

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.

from collections import deque


class Solution:
    # Time: O(n * (n + e)) where e = len(edges)
    # Space: O(n + e)

    def magnificent_sets(self, n: int, edges: list[list[int]]) -> int:
        adj: list[list[int]] = [[] for _ in range(n + 1)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        seen: list[bool] = [False] * (n + 1)
        total = 0
        for start in range(1, n + 1):
            if seen[start]:
                continue
            component = self._collect(start, adj, seen)
            best = 0
            for source in component:
                groups = self._max_groups(source, adj)
                if groups < 0:
                    return -1
                best = max(best, groups)
            total += best
        return total

    def _collect(self, start: int, adj: list[list[int]], seen: list[bool]) -> list[int]:
        component = [start]
        seen[start] = True
        stack = [start]
        while stack:
            node = stack.pop()
            for nxt in adj[node]:
                if not seen[nxt]:
                    seen[nxt] = True
                    component.append(nxt)
                    stack.append(nxt)
        return component

    def _max_groups(self, source: int, adj: list[list[int]]) -> int:
        # BFS layer count from source; -1 when an intra-layer edge breaks bipartiteness
        depth: dict[int, int] = {source: 0}
        queue: deque[int] = deque([source])
        max_depth = 0
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if nxt not in depth:
                    depth[nxt] = depth[node] + 1
                    max_depth = max(max_depth, depth[nxt])
                    queue.append(nxt)
                elif depth[nxt] == depth[node]:
                    return -1
        return max_depth + 1