Divide nodes into the maximum number of groups

Depth-First Search Breadth-First Search Union-Find Graph Theory

67.0% acceptance

Feb 25, 2026

986

You are given a positive integer n representing the number of nodes in an undirected graph. Divide nodes into m groups such that for every edge [ai,bi], |group(ai)-group(bi)|=1. Return maximum m, or -1 if impossible. Strategy: BFS-based bipartiteness check per connected component. For each component, if it's not bipartite → -1. Otherwise, per component: max groups = max over all nodes v of BFS-depth from v (longest shortest path diameter+1 computed within component).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn magnificent_sets(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n + 1];
    for e in &edges {
      adj[e[0] as usize].push(e[1] as usize);
      adj[e[1] as usize].push(e[0] as usize);
    }

    let mut color = vec![-1i32; n + 1];
    let mut comp = vec![0usize; n + 1];
    let mut comp_nodes: Vec<Vec<usize>> = Vec::new();

    // BFS to bipartite-check and find components
    for start in 1..=n {
      if color[start] != -1 { continue; }
      let cid = comp_nodes.len();
      comp_nodes.push(vec![]);
      let mut q = std::collections::VecDeque::new();
      q.push_back(start);
      color[start] = 0;
      while let Some(u) = q.pop_front() {
        comp[u] = cid;
        comp_nodes[cid].push(u);
        for &v in &adj[u] {
          if color[v] == -1 {
            color[v] = 1 - color[u];
            q.push_back(v);
          } else if color[v] == color[u] {
            return -1; // odd cycle
          }
        }
      }
    }

    // For each component, find max BFS depth from any node
    let bfs_depth = |src: usize| -> i32 {
      let mut dist = vec![-1i32; n + 1];
      dist[src] = 0;
      let mut q = std::collections::VecDeque::new();
      q.push_back(src);
      let mut max_d = 0;
      while let Some(u) = q.pop_front() {
        for &v in &adj[u] {
          if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            max_d = max_d.max(dist[v]);
            q.push_back(v);
          }
        }
      }
      max_d + 1
    };

    let mut total = 0i32;
    for cid in 0..comp_nodes.len() {
      let best = comp_nodes[cid].iter().map(|&v| bfs_depth(v)).max().unwrap();
      total += best;
    }
    total
  }
}