Divide Nodes Into the Maximum Number of Groups

Problem Description

So, you want to divide nodes into the maximum number of groups? Sounds like a party planning nightmare! Imagine trying to organize a party where you have to ensure that no two people who dislike each other end up in the same group. It’s like trying to seat your relatives at Thanksgiving dinner without starting a food fight.

In this problem, you are given n nodes and a list of edges that represent connections (or, let’s be honest, grudges) between them. Your task is to figure out how to group these nodes such that no two connected nodes are in the same group. If you can’t do it, well, it’s time to call the whole thing off!

Code Solution


class UnionFind {
 public:
  UnionFind(int n) : id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  void unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector id;
  vector rank;
};

class Solution {
 public:
  int magnificentSets(int n, vector>& edges) {
    vector> graph(n);
    UnionFind uf(n);
    unordered_map rootToGroupSize;

    for (const vector& edge : edges) {
      const int u = edge[0] - 1;
      const int v = edge[1] - 1;
      graph[u].push_back(v);
      graph[v].push_back(u);
      uf.unionByRank(u, v);
    }

    for (int i = 0; i < n; ++i) {
      const int newGroupSize = bfs(graph, i);
      if (newGroupSize == -1)
        return -1;
      const int root = uf.find(i);
      auto& groupSize = rootToGroupSize[root];
      groupSize = max(groupSize, newGroupSize);
    }

    int ans = 0;
    for (const auto& [_, groupSize] : rootToGroupSize)
      ans += groupSize;

    return ans;
  }

 private:
  int bfs(const vector>& graph, int u) {
    int step = 0;
    queue q{{u}};
    unordered_map nodeToStep{{u, 1}};

    while (!q.empty()) {
      ++step;
      for (int sz = q.size(); sz > 0; --sz) {
        const int u = q.front();
        q.pop();
        for (const int v : graph[u]) {
          if (!nodeToStep.contains(v)) {
            q.push(v);
            nodeToStep[v] = step + 1;
          } else if (nodeToStep[v] == step) {
            // There is an odd number of edges in the cycle.
            return -1;
          }
        }
      }
    }

    return step;
  }
};

Approach Explanation

The code uses a Union-Find data structure to manage the connected components of the graph. It first builds a graph from the edges and then uses a breadth-first search (BFS) to determine the size of each group while ensuring that no two connected nodes are in the same group. If it finds an odd-length cycle, it returns -1, indicating that it’s impossible to divide the nodes as required.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N + E)
Space Complexity	O(N)

Real-World Example

Think of a school where students have to be divided into groups for a project. Some students can’t work together because they just can’t stand each other (maybe they had a fight over who gets the last slice of pizza). The goal is to form the maximum number of groups without putting any feuding students together. This problem is a perfect representation of that scenario!