2493.将节点分成尽可能多的组

链接：2493.将节点分成尽可能多的组
难度：Hard
标签：广度优先搜索、并查集、图
简介：请你返回最多可以将节点分为多少个组（也就是最大的 m ）。如果没办法在给定条件下分组，请你返回 -1 。

题解 1 - cpp

• 编辑时间：2022-12-04
• 执行用时：1960ms
• 内存消耗：141.3MB
• 编程语言：cpp
• 解法介绍：先通过并查集区分不同的连通图，对每个连通图的每个点进行枚举 bfs 判断对长组。

#include <iostream>
#include <vector>
// bestlyg
# define X first
# define Y second
# define lb(x) ((x) & (-x))
# define mem(a,b) memset(a,b,sizeof(a))
# define debug freopen("r.txt","r",stdin)
# define pi pair<int,int>
#ifdef DEBUG
#define log(frm, args...) {    printf(frm, ##args); }
#else
#define log(frm, args...)
#endif
typedef long long ll;
using namespace std;
class UnionFind {
public:
    int n;
    vector<int> list;
    UnionFind(int n): n(n) {
        list = vector<int>(n);
        for (int i = 0; i < n; i++) list[i] = i;
    }
    int find(int v) {
        if (list[v] == v) return v;
        return list[v] = find(list[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 != p2) list[p1] = p2;
    }
};
class Node {
public:
    int v;
    unordered_set<int> next;
};
class Solution {
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<Node> list(n);
        UnionFind uf(n);
        for (int i = 0; i < n; i++) list[i].v = i;
        for (auto &edge : edges) {
            int v1 = edge[0] - 1, v2 = edge[1] - 1;
            list[v1].next.insert(v2);
            list[v2].next.insert(v1);
            uf.uni(v1, v2);
        }
        auto comp = [&](int start){
            // cout << "====" << start << endl;
            queue<int> q;
            q.push(start);
            unordered_set<int> used;
            unordered_map<int, unordered_set<int>> m;
            int level = 0, size = 1;
            used.insert(start);
            m[0].insert(start);
            while (q.size()) {
                int cur = q.front();
                // cout << "cur = " << cur << ", level = " << level << endl;
                q.pop();
                for (auto &next : list[cur].next) {
                    // cout << "next = " << next << ", " << used.count(next) << endl;
                    if (used.count(next)) {
                        if (m[level - 1].count(next) || m[level + 1].count(next)) continue;
                        else return -1;
                    }
                    used.insert(next);
                    m[level + 1].insert(next);
                    q.push(next);
                }
                if (--size == 0) {
                    size = q.size();
                    level++;
                }
            }
            return level;
        };
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {
            int p = uf.find(i), v = comp(i);
            if (v == -1) return -1;
            m[p] = max(m[p], v);
        }
        int ans = 0;
        for (auto &item : m) ans += item.Y;
        return ans;
    }
};