LC2493 AC

class Solution {
    vector<int> vis;
    vector<int> color;
    // int nn;
    vector<int> g[501];
    bool check_odd_ring(int u, int c) {
        if (color[u] && color[u] != c) {
            return false;
        }
        color[u] = c;
        vis[u] = 1;
        for (auto v: g[u]) {
            if (vis[v] == 0) {
                if (check_odd_ring(v, c * -1) == false) return false;
            } else if (color[v] != c * -1) {
                return false;
            }
        }
        return true;
    }
    int bfs(int u) {
        // unordered_set<int> vv;
        using pii = pair<int, int>;
        queue<pii> q;
        q.push({u, 1});
        int h = 1;
        while(q.empty() == false) {
            auto x = q.front(); q.pop();
            if (vis[x.first]) continue;
            h = max(x.second, h);
            vis[x.first] = 1;
            for (auto v: g[x.first]) {
                if (vis[v] == 0) {
                    q.push({v, x.second + 1});
                }
            }
        }
        // cout << "bfs on: " << u << " ans: " << h << endl;
        return h;
    }
    int height(int u) {
        using pii = pair<int, int>;
        queue<pii> q;
        q.push({u, 1});
        vector<int> nodes;
        int h = 1;
        while(q.empty() == false) {
            auto x = q.front(); q.pop();
            if (vis[x.first]) continue;
            h = max(x.second, h);
            nodes.push_back(x.first);
            vis[x.first] = 1;
            for (auto v: g[x.first]) {
                if (vis[v] == 0) {
                    q.push({v, x.second + 1});
                }
            }
        }
        for (auto x: nodes) {
            for (auto y: nodes) {
                vis[y] = 0;
            }
            h = max(h, bfs(x));
        }
        // cout << "h: " << h << " size: " << nodes.size() << endl;
        return h;
    }
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        for (const auto& e: edges) {
            auto u = e[0], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vis = vector<int>(n + 1);
        color = vector<int>(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (vis[i] == 0 && check_odd_ring(i, 1) == false)
                return -1;
        }
        // nn = n;
        int ans = 0;
        vis = vector<int>(n + 1);
        for (int i = 1; i <= n; ++i) {
            if (vis[i] == 0) {
                ans += height(i);
            }
        }
        return ans;
    }
};