2493. Divide Nodes Into the Maximum Number of Groups #

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.

Example 1: #

Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
Output: 4
Explanation: As shown in the image we:
- Add node 5 to the first group.
- Add node 1 to the second group.
- Add nodes 2 and 4 to the third group.
- Add nodes 3 and 6 to the fourth group.
We can see that every edge is satisfied.
It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.

Example 2: #

Input: n = 3, edges = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied.
It can be shown that no grouping is possible.

解題思路 #

先思考怎樣的情形分群會不成立，可以從範例2看到三個相連的點會失敗，如果四個五個呢？思考一下會發現奇數個節點造成的 cycle 會使得分群失敗，回傳 -1。
建立所有的 connected conponent，這可以透過 BFS/DFS/UnionFind 實作，每個conponent 會有他可以分群的最大數量，以範例 1 來說就是 5 走到 3或6 的最短距離，也就是 4。
問題變成了所有 connected conponent 最大的距離總和是多少？可以對每個點做 BFS，過程中順便檢查是否有奇數個節點的 cycle。

解法：UnionFind+BFS #

c++

class UnionFind {
public:
    unordered_map<int, int> uf;

    int find(int a) {
        if(!uf.count(a))
            uf[a] = a;
        if(uf[a] != a)
            uf[a] = find(uf[a]);
        return uf[a];
    }
    void merge(int a, int b) {
        uf[find(b)] = find(a);
    }
};

class Solution {
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        auto uf = UnionFind();
        vector<vector<int>> graph(n+1);
        for(auto edge: edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            uf.merge(edge[0], edge[1]);
        }
        
        vector<int> max_groups(n+1, 0);
        for(int i = 1; i < n+1; i++) {
            deque<pair<int, int>> queue = {{i, 1}};
            vector<int> visited(n+1, 0);
            visited[i] = 1;
            while(!queue.empty()) {
                auto pop = queue.front();
                int cur = pop.first, level = pop.second;
                queue.pop_front();
                for(auto& edge: graph[cur]) {
                    if(!visited[edge]) {
                        queue.push_back({edge, level+1});
                        visited[edge] = level+1;
                    }

                    if(level == visited[edge])
                        return -1;
                }
                int root = uf.find(i);
                max_groups[root] = max(max_groups[root], level);
            }
        }
        int res = 0;
        for(int ele: max_groups)
            res+=ele;
        return res;
    }
};

python

class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind()
        graph = defaultdict(list)
        for e1, e2 in edges:
            graph[e1].append(e2)
            graph[e2].append(e1)
            uf.union(e1, e2)
        max_groups = [0]*(n+1)
        for i in range(1, n+1):
            q = deque([(i, 1)])
            visited = [0]*(n+1)
            visited[i] = 1
            m = 0
            while q:
                curr, level = q.popleft()
                m = max(m, level)
                for edge in graph[curr]:
                    if not visited[edge]:
                        q.append([edge, level+1])
                        visited[edge] = level+1
                    if level == visited[edge]:
                        return -1
            root = uf.find(i)
            max_groups[root] = max(max_groups[root], m)
        return sum(max_groups)


class UnionFind:
    def __init__(self):
        self.uf = {}

    def union(self, a, b):
        roota = self.find(a)
        rootb = self.find(b)
        self.uf[rootb] = roota

    def find(self, a):
        if a not in self.uf:
            self.uf[a] = a
        if self.uf[a] != a:
            self.uf[a] = self.find(self.uf[a])
        return self.uf[a]