203. Divide Nodes Into the Maximum Number of Groups

🔗 LeetCode Problem: 2493. Divide Nodes Into the Maximum Number of Groups
📊 Difficulty: Hard
🏷️ Topics: Graph, BFS, DFS, Union-Find, Bipartite, Connected Components

Problem Statement

You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.

You are also given a 2D integer array edges, where edges[i] = [aᵢ, bᵢ] indicates that there is a bidirectional edge between nodes aᵢ and bᵢ. Notice that the given graph may be disconnected.

Divide the nodes of the graph into m groups (1-indexed) such that: - Each node in the graph belongs to exactly one group. - For every pair of nodes in the graph that are connected by an edge [aᵢ, bᵢ], if aᵢ belongs to the group with index x, and bᵢ belongs to the group with index y, then |x - y| = 1.

Return the maximum number of groups (i.e., maximum m) that you can divide the nodes into.

Example 1:

Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]

Visual:
    1 --- 2 --- 3
    |     |
    4     6
    |
    5

Output: 4

Explanation:
  One valid grouping:
    Group 1: {1}
    Group 2: {2, 4, 5}
    Group 3: {3, 6}
    Group 4: {} or not used

  Wait, let me recalculate...

  BFS levels from node 1:
    Level 0: {1}
    Level 1: {2, 4, 5}
    Level 2: {3, 6}

  Maximum groups = 3? But answer is 4...

  Try from different starting nodes!
  BFS from node 3:
    Level 0: {3}
    Level 1: {2}
    Level 2: {1, 6}
    Level 3: {4, 5}

  4 groups! ✅

Example 2:

Input: n = 3, edges = [[1,2],[2,3],[3,1]]

Visual:
  Triangle:
    1
   / \
  2---3

Output: -1

Explanation:
  This is a triangle (odd cycle).
  Cannot satisfy |x - y| = 1 for all edges.
  For example, if we assign:
    1 → group 1
    2 → group 2 (edge 1-2: |1-2| = 1 ✅)
    3 → group 3 (edge 2-3: |2-3| = 1 ✅)
    But edge 3-1: |3-1| = 2 ❌

  Impossible! Return -1.

Constraints: - 1 <= n <= 500 - 1 <= edges.length <= 10⁴ - edges[i].length == 2 - 1 <= aᵢ, bᵢ <= n - aᵢ != bᵢ - There is at most one edge between any pair of vertices.

---

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving 🤔

Divide nodes into MAXIMUM number of groups: 📊

Constraint: Adjacent nodes must be in consecutive groups!
  |group(u) - group(v)| = 1

This is MUCH harder than bipartite! 🔥

Bipartite (Problems 201/202):
  2 groups only: {A, B}
  Adjacent → different groups

This problem:
  m groups: {1, 2, 3, ..., m}
  Adjacent → consecutive groups (differ by 1)

Example visualization:

Graph:  1 --- 2 --- 3

Bipartite would give:
  Group A: {1, 3}
  Group B: {2}
  → 2 groups

This problem wants:
  Group 1: {1}
  Group 2: {2}
  Group 3: {3}
  → 3 groups! ✅ Maximum!

Goal: Maximize number of groups! 🎯

Understanding the Constraint 💡

Constraint: |group(u) - group(v)| = 1

What does this mean?

If edge u --- v exists:
  - If u in group 3, then v in group 2 or 4
  - Adjacent nodes in CONSECUTIVE groups only!

Example 1: Linear path ✅
  1 --- 2 --- 3 --- 4

  Assign:
    1 → group 1
    2 → group 2 (|1-2| = 1 ✅)
    3 → group 3 (|2-3| = 1 ✅)
    4 → group 4 (|3-4| = 1 ✅)

  4 groups possible! Maximum!

Example 2: Triangle ❌
  1 --- 2
   \   /
    \ /
     3

  Assign:
    1 → group 1
    2 → group 2 (|1-2| = 1 ✅)
    3 → group 3 (|2-3| = 1 ✅)

  But edge 1-3: |1-3| = 2 ❌

  Impossible! Odd cycle breaks it!

Key insight: Odd cycles make it IMPOSSIBLE! 🔑

Connection to Bipartite 🔗

CRITICAL CONNECTION:

If graph has odd cycle:
  → NOT bipartite
  → CANNOT do this grouping at all!
  → Return -1 ❌

If graph is bipartite:
  → No odd cycles
  → Grouping is POSSIBLE! ✅
  → Find the MAXIMUM number of groups

So this problem has TWO parts:

Part 1: Check if bipartite (any odd cycle?)
  NO → return -1
  YES → proceed to part 2

Part 2: Find maximum groups
  BFS from each node as starting point
  Count BFS levels (each level = one group)
  Return maximum across all starting nodes

Why try all starting nodes?
  Different starting points give different groupings!

The BFS Layering Insight 🌊

BFS naturally creates layers!

Graph:  1 --- 2 --- 3 --- 4

BFS from node 1:
  Layer 0: {1}     → Group 1
  Layer 1: {2}     → Group 2
  Layer 2: {3}     → Group 3
  Layer 3: {4}     → Group 4

  4 groups! ✅

BFS from node 2:
  Layer 0: {2}     → Group 1
  Layer 1: {1, 3}  → Group 2
  Layer 2: {4}     → Group 3

  3 groups only!

Maximum = 4 (from starting at node 1)

BFS levels = Valid grouping! 🎯
Adjacent nodes always in adjacent levels!

---

🧠 The Journey - Building Intuition

Part 1: Understanding "Consecutive Groups" 🎯

💭 What does |group(u) - group(v)| = 1 really mean?

Think of groups as LAYERS in a building:
  - Layer 1 (ground floor)
  - Layer 2 (first floor)
  - Layer 3 (second floor)
  - ...

Constraint: If two nodes are connected,
they must be on ADJACENT floors!

Can't have edge between floor 1 and floor 3!
Must be: 1↔2, 2↔3, 3↔4, etc.

This is like BFS levels! 💡

BFS from a starting node:
  - Start node: Level 0 (floor 1)
  - Its neighbors: Level 1 (floor 2)
  - Their neighbors: Level 2 (floor 3)
  - ...

BFS levels satisfy the constraint automatically!
Adjacent nodes always differ by 1 level! ✅

Part 2: Why Odd Cycles Break Everything 🔄

💭 Let's see why odd cycle is impossible:

Triangle (3-cycle):
    1
   / \
  2---3

Try to assign groups:
  1 → group 1
  2 → group 2 (edge 1-2: |1-2| = 1 ✅)
  3 → group ? 

  Edge 1-3 requires: |1-?| = 1 → ? = 0 or 2
  Edge 2-3 requires: |2-?| = 1 → ? = 1 or 3

  Only ? = 2 satisfies edge 1-3
  But then edge 2-3: |2-2| = 0 ❌

  Contradiction!

Similarly with ? = 3:
  Edge 2-3: |2-3| = 1 ✅
  But edge 1-3: |1-3| = 2 ❌

No valid assignment! Odd cycle = impossible!

Even cycle (4-cycle) works:
  1 --- 2
  |     |
  4 --- 3

  1 → group 1
  2 → group 2
  3 → group 3
  4 → group 2 (or could be group 4)

  All constraints satisfied! ✅

Odd cycle ⟺ NOT bipartite ⟺ Impossible! 🔑

Part 3: Why Try All Starting Nodes? 🚀

💭 Different starting nodes give different results!

Graph:  1 --- 2 --- 3

Start from 1:
  Level 0: {1}
  Level 1: {2}
  Level 2: {3}
  → 3 levels (3 groups)

Start from 2:
  Level 0: {2}
  Level 1: {1, 3}
  → 2 levels (2 groups)

Start from 3:
  Level 0: {3}
  Level 1: {2}
  Level 2: {1}
  → 3 levels (3 groups)

Maximum = 3! ✅

Why different?
  Starting from middle node gives fewer levels!
  Starting from "end" nodes gives more levels!

To find maximum:
  Must try ALL nodes as starting points!
  Return the maximum BFS depth found! 🎯

Part 4: Handling Disconnected Components 🗺️

💭 Graph might be disconnected!

Example:
  Component 1: 1 --- 2 --- 3
  Component 2: 4 --- 5

Strategy:
  1. Find all connected components
  2. Check EACH component for odd cycles
     - If ANY has odd cycle → return -1 ❌
  3. For EACH component, find max BFS depth
     - Try all nodes in that component
  4. Return sum of max depths across components

Why sum?
  Each component independent!
  Can reuse group numbers in each component!

  Component 1: groups 1, 2, 3 (max = 3)
  Component 2: groups 1, 2 (max = 2)

  Total: 3 + 2 = 5 groups! ✅

Each component contributes its maximum! 🎯

Part 5: The Complete Algorithm 📝

✨ Complete strategy:

STEP 1: Build graph from edges
  Adjacency list representation

STEP 2: Find all connected components
  DFS/BFS to identify components

STEP 3: For each component:

  SUB-STEP 3.1: Check if bipartite
    Run bipartite check (BFS 2-coloring)
    If NOT bipartite → return -1 ❌

  SUB-STEP 3.2: Find max BFS depth
    Try BFS from every node in component
    Track maximum depth reached
    This is max groups for this component

STEP 4: Sum max groups across components
  Total = sum of all component maximums
  Return total! ✅

Time complexity:
  Each BFS: O(V + E)
  Try from all nodes: O(V) BFSs
  Total: O(V × (V + E)) per component

For small graphs (n ≤ 500), this is fine! ⚡

---

🎯 Approach: BFS Multi-Start (Complete Solution!)

The Key Insight 💡

Two-phase algorithm: First check if ANY component has odd cycle (bipartite check) 🔍. If yes → return -1 ❌. Otherwise, for EACH component, try BFS from EVERY node as starting point 🚀, count BFS levels (each level = group), track maximum 📊! Sum maximums across all components because they're independent! 🗺️ Time: O(n × (n + E)) ⚡, Space: O(n + E) 📦!

Multi-start BFS finds optimal! 🌟

Complete Implementation

class Solution {
    public int magnificentSets(int n, int[][] edges) {
        // ═══════════════════════════════════════════════════
        // MULTI-START BFS APPROACH 🌊
        // ═══════════════════════════════════════════════════
        // 1. Build graph
        // 2. Find connected components
        // 3. Check each component for odd cycles
        // 4. Find max BFS depth for each component
        // 5. Sum maximums
        // ═══════════════════════════════════════════════════

        // ═══════════════════════════════════════════════════
        // STEP 1: BUILD GRAPH 📊
        // ═══════════════════════════════════════════════════
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // ═══════════════════════════════════════════════════
        // STEP 2: FIND CONNECTED COMPONENTS 🗺️
        // ═══════════════════════════════════════════════════
        boolean[] visited = new boolean[n + 1];
        List<List<Integer>> components = new ArrayList<>();

        for (int node = 1; node <= n; node++) {
            if (!visited[node]) {
                List<Integer> component = new ArrayList<>();
                dfsComponent(graph, node, visited, component);
                components.add(component);
            }
        }

        // ═══════════════════════════════════════════════════
        // STEP 3 & 4: PROCESS EACH COMPONENT 🎯
        // ═══════════════════════════════════════════════════
        int totalGroups = 0;

        for (List<Integer> component : components) {
            // ───────────────────────────────────────────────
            // CHECK IF BIPARTITE (no odd cycle) ✅
            // ───────────────────────────────────────────────
            if (!isBipartite(graph, component)) {
                return -1;  // Has odd cycle! Impossible! ❌
            }

            // ───────────────────────────────────────────────
            // FIND MAX BFS DEPTH IN THIS COMPONENT 🚀
            // ───────────────────────────────────────────────
            int maxDepth = 0;
            for (int startNode : component) {
                int depth = bfsMaxDepth(graph, startNode, n);
                maxDepth = Math.max(maxDepth, depth);
            }

            totalGroups += maxDepth;
        }

        return totalGroups;
    }

    // ═══════════════════════════════════════════════════════
    // DFS: Find all nodes in current component 🔍
    // ═══════════════════════════════════════════════════════
    private void dfsComponent(List<List<Integer>> graph, int node,
                              boolean[] visited, List<Integer> component) {
        visited[node] = true;
        component.add(node);

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfsComponent(graph, neighbor, visited, component);
            }
        }
    }

    // ═══════════════════════════════════════════════════════
    // CHECK: Is component bipartite? (no odd cycle) 🔍
    // ═══════════════════════════════════════════════════════
    private boolean isBipartite(List<List<Integer>> graph, 
                                List<Integer> component) {
        Map<Integer, Integer> color = new HashMap<>();

        for (int node : component) {
            if (!color.containsKey(node)) {
                // BFS 2-coloring from this node
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(node);
                color.put(node, 0);

                while (!queue.isEmpty()) {
                    int curr = queue.poll();
                    int currColor = color.get(curr);

                    for (int neighbor : graph.get(curr)) {
                        if (!color.containsKey(neighbor)) {
                            color.put(neighbor, 1 - currColor);
                            queue.offer(neighbor);
                        } else if (color.get(neighbor) == currColor) {
                            return false;  // Odd cycle! ❌
                        }
                    }
                }
            }
        }

        return true;  // Bipartite! ✅
    }

    // ═══════════════════════════════════════════════════════
    // BFS: Find maximum depth from starting node 🌊
    // ═══════════════════════════════════════════════════════
    private int bfsMaxDepth(List<List<Integer>> graph, int start, int n) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        dist[start] = 0;

        int maxDist = 0;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int neighbor : graph.get(node)) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    maxDist = Math.max(maxDist, dist[neighbor]);
                    queue.offer(neighbor);
                }
            }
        }

        // Return number of levels (groups)
        // maxDist is 0-indexed, so add 1
        return maxDist + 1;
    }
}

Why This Works 🎯

Component-wise processing: 🗺️ - Each component independent - Can reuse group numbers - Sum of maximums = total groups!

Bipartite check first: 🔍 - Odd cycle → impossible (-1) - Must check BEFORE trying to find max - Saves time if impossible!

Multi-start BFS: 🚀 - Different starting points → different depths - Must try ALL nodes to find maximum - BFS levels = valid grouping!

Distance tracking: 📊 - dist[node] = BFS level - Level 0, 1, 2, ... = Groups 1, 2, 3, ... - maxDist + 1 = number of groups!

---

📝 Quick Revision Notes

🎯 Core Concept

Maximum Groups = advanced bipartite! 🔥 Constraint: adjacent nodes in consecutive groups (|x-y|=1) 📊! Two phases: (1) Check if bipartite - odd cycle → return -1 ❌. (2) Find max groups - try BFS from every node, count levels, take maximum! 🚀 For disconnected components, sum maximums 🗺️! Time: O(n²+nE) ⚡, Space: O(n+E) 📦! BFS levels = valid grouping! 🌊

⚡ Quick Algorithm

1. Build graph + find components
2. For each component:
   - Check bipartite (any odd cycle? → return -1)
   - Try BFS from every node
   - Track max BFS depth
3. Sum maximums across components
4. Return total

Implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution {
  public int magnificentSets(int n, int[][] a) {
    int res = 0;

    // step 1: build graph from edges.
    List<List<Integer>> adjList = getAdjList(n, a);

    // step 2: find connected components through DFS at each node.
    List<List<Integer>> components = getComponentsDFS(n, adjList);

    // step 3: process each component - check if bipartite and max BFS depth.
    for (List<Integer> component : components) {
      // Step 3a: if this component is not Bipartite, we cannot
      // divide the graph into groups.
      if (!isBipartite(component, adjList)) {
        return -1;
      }

      // Stpe 3b: start BFS from each node of each of the components.
      // Find max depth, a traversal can go from each node.
      int maxDepth = 0;
      for (int node : component) {
        maxDepth = Math.max(maxDepth, getDepthBFS(node, adjList));
      }

      res = res + maxDepth;
    }

    return res;
  }

  private int getDepthBFS(int start, List<List<Integer>> adjList) {
    HashSet<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited.add(start);
    int depth = 0;

    while (!queue.isEmpty()) {
      int size = queue.size();

      for (int i = 0; i < size; i++) {
        int curr = queue.poll();
        for (int j : adjList.get(curr)) {
          if (!visited.contains(j)) {
            queue.offer(j);
            visited.add(j);
          }
        }
      }

      depth++;
    }

    return depth;
  }

  private boolean isBipartite(List<Integer> component, List<List<Integer>> adjList) {
    Map<Integer, Integer> color = new HashMap<>();

    for (int start : component) {
      if (color.containsKey(start)) {
        continue;
      }

      // color it only when its uncolored
      color.put(start, 0);

      Queue<Integer> queue = new LinkedList<>();
      queue.offer(start);

      while (!queue.isEmpty()) {
        int currNode = queue.poll();

        int currNodeColor = color.get(currNode);
        int nextNodeColor = 1 - currNodeColor; // 0 becomes 1 and 1 becomes 0

        for (int j : adjList.get(currNode)) {
          if (!color.containsKey(j)) {
            color.put(j, nextNodeColor);
            queue.offer(j);
          } else if (color.get(j) == currNodeColor) {
            return false;
          }
        }
      }
    }

    // Graph is bipartite
    return true;
  }

  private List<List<Integer>> getComponentsDFS(int n, List<List<Integer>> adjList) {
    List<List<Integer>> components = new ArrayList<>();
    HashSet<Integer> visited = new HashSet<>();

    // DO DFS from each node and check the individual components.
    for (int i = 1; i <= n; i++) {
      if (!visited.contains(i)) {
        List<Integer> curr = new ArrayList<>();
        visited.add(i);
        dfsUtil(i, visited, adjList, curr);
        components.add(curr);
      }
    }

    return components;
  }

  private void dfsUtil(int node, HashSet<Integer> visited, List<List<Integer>> adjList, List<Integer> curr) {
    curr.add(node);
    for (int i : adjList.get(node)) {
      if (!visited.contains(i)) {
        visited.add(i);
        dfsUtil(i, visited, adjList, curr);
      }
    }
  }

  private List<List<Integer>> getAdjList(int n, int[][] edges) {
    List<List<Integer>> adjList = new ArrayList<>();

    for (int i = 0; i <= n; i++) {
      adjList.add(new ArrayList<>());
    }

    for (int[] edge : edges) {
      adjList.get(edge[0]).add(edge[1]);
      adjList.get(edge[1]).add(edge[0]);
    }

    return adjList;
  }

  public static void main(String[] args) {
    Solution s = new Solution();

    System.out
        .println(s.magnificentSets(6, new int[][] { { 1, 2 }, { 1, 4 }, { 1, 5 }, { 2, 6 }, { 2, 3 }, { 4, 6 } })); // 4
    System.out.println(s.magnificentSets(3, new int[][] { { 1, 2 }, { 2, 3 }, { 3, 1 } })); // -1
  }
}

🎪 Memory Aid

"Odd cycle breaks, return minus one" ❌
"Try all starts, each BFS run" 🚀
"Levels are groups, track the max" 📊
"Sum components, that's the facts!" 🗺️ ✨

⚠️ Don't Forget

• Check bipartite FIRST - odd cycle → impossible! 🔍
• Try ALL starting nodes - different starts give different depths! 🚀
• BFS levels = groups - adjacent nodes in adjacent levels! 🌊
• Sum across components - each independent! 🗺️
• Add 1 to maxDist - levels are 0-indexed! 📊
• 1-indexed nodes - graph size n+1! ⚠️

---

🎉 Congratulations!

You've mastered an ADVANCED bipartite problem! 🔥

What You Learned:

✅ Consecutive group constraint - |x-y|=1 for edges! 📊
✅ Bipartite prerequisite - odd cycle → impossible! 🔍
✅ Multi-start BFS - try all starting points! 🚀
✅ BFS levels as groups - natural grouping! 🌊
✅ Component independence - sum maximums! 🗺️
✅ Optimization strategy - find maximum depth! 🎯

The Beautiful Progression:

Problem 201: Is Graph Bipartite?
  ├─ Check: Can 2-color?
  ├─ Tool: BFS/DFS
  └─ Goal: Yes/No

Problem 202: Possible Bipartition
  ├─ Same as 201 with different input
  ├─ Transform: pairs → graph
  └─ Goal: Yes/No

Problem 203: Maximum Groups ⭐
  ├─ Check: Has odd cycle? (bipartite)
  ├─ If no: Find MAXIMUM groups
  ├─ Tool: Multi-start BFS
  └─ Goal: Maximum number!

Progression: Basic → Application → Optimization! 🚀

Twenty-six problems completed! 🎉
Advanced bipartite mastered! You can now handle constraint satisfaction, optimization, and multi-layering! 💪✨🎯🌊📊🔥