2493: Divide-Nodes-Into-the-Maximum-Number-of-Groups
Hard

table of contents

This question is currently the “bane” of my “existence”.

First thing to note, that the requirement “For every pair of nodes in the graph that are connected by an edge [a_i, b_i], if a_i belongs to the group with index x, and b_i belongs to the group with index y, then |y - x| = 1” is only satisfied if there does not exist an odd cycle in the graph. Now, since a graph is bipartite if and only it does not have an odd-length cycle, we just need to prove that this graph is bipartite.

We can do this with breadth-first search, as we can alternate between 2 values and allocate 1 to each adjacent node. If we see a visited node, we can check if the values match (and alternate properly) before breaking; else, we can return -1 immediately.

Now, to find the maximum number of groups is just a boujee way of saying find the maximum shortest distance between any 2 nodes. We can simply do this by running BFS through all the nodes in the graph. Simple enough right?

Unfortunately, life is never this easy. They mentioned that the given graph may be disconnected? This basically means, we have to repeat the previous 2 steps for each disjoint graph and sum up all the maximum shortest distances. This is because the nodes in separate disjoint graphs are never connected (might just be stating the obvious here), so we can place each node from separate disjoint graphs, into separate groups to maximimise the number of groups present.

Now, all we need to do is put the above into code. Easy, right?!?!?!

code

class Solution {
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adjacencyMatrix(n);

        for (auto &edge : edges) {
            adjacencyMatrix[edge[0]-1].push_back(edge[1]-1);
            adjacencyMatrix[edge[1]-1].push_back(edge[0]-1);
        }

        int ans = 0;
        int max_distance = 0;
        int distance = 0;
        vector <int> seen (n); 
        for (int i = 0; i < n; ++i) {
            if (seen[i] != 0) continue;

            queue<int> disjoint_nodes;
            disjoint_nodes.push(i);
            max_distance = 0;

            while (!disjoint_nodes.empty()) {
                int initial_node = disjoint_nodes.front();
                disjoint_nodes.pop();

                queue<int> nodes;
                vector<int> traversed (n);

                distance = 0;
                nodes.push(initial_node);
                seen[initial_node] = -1;
                traversed[initial_node] = 1;

                while (!nodes.empty()) {
                    int m = nodes.size();
                    for (int temp = 0; temp < m; ++temp) {
                        int front = nodes.front();
                        nodes.pop();
        
                        for (int node : adjacencyMatrix[front]) {
                            if (node == seen[front]-2) {
                                continue;
                            }
        
                            if (traversed[node] == 0) {
                                traversed[node] = traversed[front] ^ 2;
                                nodes.push(node);
                                seen[node] = front+2;
                                if (max_distance == 0) {
                                    disjoint_nodes.push(node);
                                }
                            } else if ((traversed[node] ^ 2) != traversed[front]) {
                                return -1;
                            }
                        }
                    }
                    ++distance;
                }

                max_distance = max(max_distance, distance);
            }
            ans += max_distance;
        }
        
        return ans;
    }
};

complexity