2493. Divide Nodes Into the Maximum Number of Groups

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] = [ai, bi] indicates that there is a bidirectional edge between nodes ai and bi. 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 [ai, bi], if ai belongs to the group with index x, and bi belongs to the group with index y, then |y - x| = 1.

Return the maximum number of groups (i.e., maximum m) into which you can divide the nodes. Return -1 if it is impossible to group the nodes with the given conditions.

int uf[555];
int find(int u) {
    return uf[u] == u ? u : uf[u] = find(uf[u]);
}
void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu, pv);
}
class Solution {
    int bfs(vector<vector<int>>& adj, int u, int n) {
        vector<int> dep(n + 1, -1);
        dep[u] = 1;
        queue<int> q;
        q.push(u);
        int res = 1;
        while(q.size()) {
            auto u = q.front(); q.pop();
            for(auto& v : adj[u]) {
                if(dep[v] == -1) {
                    dep[v] = dep[u] + 1;
                    res = max(res, dep[v]);
                    q.push(v);
                } else {
                    if(abs(dep[v] - dep[u]) != 1) return -1;
                }
            }
        }
        return res;
    }
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n + 1);
        iota(begin(uf), end(uf),0);
        for(auto e : edges) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
            uni(u,v);
        }
        int res = 0;
        unordered_map<int, int> mp;
        for(int i = 1; i <= n; i++) {
            int pi = find(i);
            mp[pi] = max(mp[pi], bfs(adj,i,n));
        }
        for(auto [_, v] : mp) {
            if(v == 0) return -1;
            res += v;
        }
        return res;
    }
};