# LeetCode 2493. Divide Nodes Into the Maximum Number of Groups

https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/description/

## 題目大意

給無向圖 $G= (V,E)$ ，要將頂點分組：

- 每個頂點必須屬於唯一的組（不能重複出現在多個組）
- 如果兩個頂點之間有邊，它們所屬的組別索引必須相差 $1$ (從 $1$ 開始編號)：

$$
\left| group(u) − group(v) \right| = 1, \forall (u,v)\in E
$$

也就是說，如果某個頂點 $u$ 在組 $\alpha$，那麼與 $u$ 直接相連的頂點 $v$ 只能在編號 $\alpha\pm 1$ 的那組

回傳最多能劃分幾組？若無法劃分，回傳 $-1$

(題目不保證圖連通)

## 思考

這題你要能看出它有點考到 bipartite

這邊我用 union find 找連通分量、用 DFS 判斷二分性，最後用 BFS 這樣 level 的遍歷順序找出最佳解

### C++ 參考解答

class DisjointSet
{
public:
    DisjointSet(size_t n) : parent(n), rank(n)
    {
        iota(parent.begin(), parent.end(), 0);
    }

    void unionSet(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY)
            return;

        if (rank[rootX] > rank[rootY])
            swap(rootX, rootY);
        parent[rootX] = rootY;
        if (rank[rootX] == rank[rootY])
            ++rank[rootX];
    }

    int find(int x) { return parent[x] == x ? parent[x] : parent[x] = find(parent[x]); }

private:
    vector<int> parent;
    vector<int> rank;
};

enum class Color : char
{
    UNCOLORED,
    BLUE,
    RED,
};

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

        for (const auto &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.unionSet(u, v);
        }

        vector<vector<int>> components(n);
        vector<Color> nodeColor(n, Color::UNCOLORED);

        for (int i = 0; i < n; ++i)
        {
            if (nodeColor[i] == Color::UNCOLORED)
            {
                const int root = uf.find(i);
                if (!dfs(i, Color::BLUE, graph, nodeColor, components[root]))
                    return -1;
            }
        }

        int ans = 0;
        for (const auto &component : components)
        {
            if (!component.empty())
                ans += bfs(component, graph);
        }

        return ans;
    }

private:
    bool dfs(int node, Color color, const vector<vector<int>> &graph, vector<Color> &nodeColor, vector<int> &component)
    {
        nodeColor[node] = color;
        component.push_back(node);

        for (int neighbor : graph[node])
        {
            if (nodeColor[neighbor] == color)
                return false;
            if (nodeColor[neighbor] == Color::UNCOLORED && !dfs(neighbor, color == Color::BLUE ? Color::RED : Color::BLUE, graph, nodeColor, component))
                return false;
        }

        return true;
    }

    int bfs(const vector<int> &component, const vector<vector<int>> &graph)
    {
        int maxDepth = 0;
        for (int node : component)
        {
            queue<int> q;
            vector<int> depth(graph.size(), -1);
            q.push(node);
            depth[node] = 1;

            int level = 1;
            while (!q.empty())
            {
                const int u = q.front();
                q.pop();

                for (int v : graph[u])
                {
                    if (depth[v] == -1)
                    {
                        q.push(v);
                        depth[v] = depth[u] + 1;
                        level = max(level, depth[v]);
                    }
                }
            }

            maxDepth = max(maxDepth, level);
        }

        return maxDepth;
    }
};

這題 code 本身不難 (應該說難點不在這)，但怎麼看透題目是真的不容易
我也是想了好久，直到我看到 Hint 1


### Go 參考解答

(累了，沒寫...)