[LeetCode] 2493. Divide Nodes Into the Maximum Number of Groups

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

leetcode - Divide Nodes Into the Maximum Number of Groups

문제 유형: bfs, 그래프, 연결 컴포넌트, 이분 그래프

문제 난이도: Hard

 

문제

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.

 

1~n의 라벨이 붙은 노드들의 무방향 그래프가 있다.

2D정수배열 edges가 주어진다. 양방향 간선임을 의미한다.

 

그래프의 노드는 하나의 그룹에 있어야 한다.

각 노드간 간선이 존재하면, 인접한 그룹이어야 한다.

 

최대 그룹의 개수를 구하시오. 불가능하면 -1을 반환하시오.

 

풀이

우선, 모든 그래프는 이분 그래프여야 한다. 그렇지 않으면 조건대로 그룹을 형성할 수 없다. 각 연결 컴포넌트들은 두 개의 분리집합으로 나뉘어야 한다.

 

그리고, 각 연결 컴포넌트들에 대해 가장 긴 두 노드간의 거리를 구하면 된다. 그 거리 +1의 값들을 모두 누적한다.

 

 

코드

C++

class Solution {
public:
    int maxBFS(int root, vector<vector<int>>& adj) {
        vector<int> dist(adj.size(), INT_MAX);
        queue<int> q;
        q.push(root);
        dist[root] = 0;
        int res = 0;

        while(!q.empty()) {
            int curr = q.front();
            q.pop();

            for(const auto &next : adj[curr]) {
                if(dist[next] > dist[curr]+1) {
                    dist[next] = dist[curr]+1;
                    res = max(res, dist[next]);
                    q.push(next);
                }
            }
        }

        return res+1;
    }

    bool isBipartite(int root, int col, int componentId, vector<vector<int>>& adj, vector<int>& color, vector<int>& component, vector<vector<int>>& components) {
        queue<int> q;
        q.push(root);
        color[root] = col;
        component[root] = componentId;
        components[componentId].push_back(root);

        while(!q.empty()) {
            int curr = q.front();
            q.pop();

            for(const auto &next : adj[curr]) {
                if(color[next] == color[curr]) return false;
                if(color[next] == -1) {
                    color[next] = color[curr] ^ 1;
                    component[next] = componentId;
                    components[componentId].push_back(next);
                    q.push(next);
                }
            }
        }

        return true;
    }

    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n+1);

        for(const auto &edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<int> color(n+1, -1);
        vector<int> component(n+1, -1);
        int compId = 0;

        vector<vector<int>> components;

        for(int i = 1; i <= n; ++i) {
            if(color[i] == -1) {
                components.push_back({});
                if(!isBipartite(i, 0, compId, adj, color, component, components)) return -1;
                compId++;
            }
        }
        

        int ans = 0;

        for(const auto &comp : components) {
            int maxDist = 0;
            for(const auto &node : comp) {
                maxDist = max(maxDist, maxBFS(node, adj));
            }
            ans += maxDist;
        }

        return ans;
    }
};