_2493. Divide Nodes Into the Maximum Number of Groups.md

2493. Divide Nodes Into the Maximum Number of Groups

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : January 30, 2025

Last updated : January 30, 2025

---

Related Topics : Depth-First Search, Breadth-First Search, Union Find, Graph

Acceptance Rate : 67.5 %

---

Notes

• Convert edges into a two way mapping via a defaultdict

• Track all visited nodes

• Parse from a random starting node

• Repeat from a random non visited node in case it's a disconnected graph

• Groupings are partially based on cycles that exist

  • E.g. in example 1, there's a cycle that's 1-2-6-4-1
  • These maximize the grouping spread of those nodes in particular, limiting it to cycle_size / 2
  • If a cycle is odd, it's impossible

Idea:

• Is the answer just the longest independent line ignoring cycles
• Returning -1 no answer if there's an odd cycle

Update: 49/55 test cases

• My worry was true, cycles won't always end up being the longest independent line.
• I need to calculate the lengths of each vistigial branch out from a cycle, and find which of the two ways around the cycle is smaller since the other branch will just "fold up"

Plan:

• I have a feeling that brute forcing the farthest distance from each individual point is pbly within AC range for the constraints... As much as I want to deny it and not want to implement it since I've spent so long working on a more efficient Solution

... I hate that I was right...

---

Solutions

• h2493.py

Python

h2493.py

class Solution:
    # output: (dist, node_no)
    def furthest_vertex(self, curr_node: int, edges: DefaultDict[int, Set[int]], visited: Set[int] = None) -> Tuple[int, int] :
        if not visited :
            visited = set()
        nxt_to_visit = deque([(1, curr_node)])
        farthest = (-1, -1)
        while nxt_to_visit :
            dist, curr = nxt_to_visit.popleft()

            if curr in visited :
                continue
            visited.add(curr)

            if dist > farthest[0] :
                farthest = (dist, curr)

            for nxt in edges[curr] :
                if nxt in visited :
                    continue
                nxt_to_visit.append((dist + 1, nxt))

        return farthest

    def odd_cycle_len(self, 
                      curr_node: int, 
                      traversal_no: int, 
                      edges: DefaultDict[int, Set[int]], 
                      visited: Dict[int, int] = None) -> bool :
        if curr_node in visited :
            return (traversal_no - visited[curr_node]) % 2 != 0

        visited[curr_node] = traversal_no

        return any(self.odd_cycle_len(x, traversal_no + 1, edges, visited) for x in edges[curr_node])

    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        # Edge list from each vertex
        e = defaultdict(set)
        for u, v in edges :
            e[u].add(v)
            e[v].add(u)

        groups = 0

        to_visit = set(range(1, n + 1))
        while to_visit :
            curr = to_visit.pop()

            visited = {}
            if self.odd_cycle_len(curr, 1, e, visited) :
                return -1

            to_visit -= visited.keys()
            groups += max([self.furthest_vertex(x, e) for x in visited.keys()])[0]

        return groups