2493. Divide Nodes Into the Maximum Number of Groups Hard

1/**
2 * [2493] Divide Nodes Into the Maximum Number of Groups
3 *
4 * You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.
5 * 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.
6 * Divide the nodes of the graph into m groups (1-indexed) such that:
7 * 
8 * 	Each node in the graph belongs to exactly one group.
9 * 	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.
10 * 
11 * 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.
12 *  
13 * <strong class="example">Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2022/10/13/example1.png" style="width: 352px; height: 201px;" />
15 * Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
16 * Output: 4
17 * Explanation: As shown in the image we:
18 * - Add node 5 to the first group.
19 * - Add node 1 to the second group.
20 * - Add nodes 2 and 4 to the third group.
21 * - Add nodes 3 and 6 to the fourth group.
22 * We can see that every edge is satisfied.
23 * 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.
24 * 
25 * <strong class="example">Example 2:
26 * 
27 * Input: n = 3, edges = [[1,2],[2,3],[3,1]]
28 * Output: -1
29 * 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.
30 * It can be shown that no grouping is possible.
31 * 
32 *  
33 * Constraints:
34 * 
35 * 	1 <= n <= 500
36 * 	1 <= edges.length <= 10^4
37 * 	edges[i].length == 2
38 * 	1 <= ai, bi <= n
39 * 	ai != bi
40 * 	There is at most one edge between any pair of vertices.
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/
46// discuss: https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn magnificent_sets(n: i32, edges: Vec<Vec<i32>>) -> i32 {
52        0
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_2493() {
64    }
65}
66