Problem

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.

Examples

Example 1:

graph LR;
	subgraph "Group 1";
		A((5))
	end
	subgraph "Group 2";
		B((1))
	end
	subgraph "Group 3";
		C((2))
		D((4))
	end
	subgraph "Group 4";
		E((3))
		F((6))
	end

A --- B
B --- C
B --- D
C --- E
C --- F
D --- F
  

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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:

1
2
3
4

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.

Constraints:

  • 1 <= n <= 500
  • 1 <= edges.length <= 104
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • ai != bi
  • There is at most one edge between any pair of vertices.

Solution

Method 1 - Using DFS and BFS

Here is the approach:

  1. Graph Construction: Construct the adjacency list representation of the graph from the edges.
  2. Graph Coloring and Connected Components: Use Depth-First Search (DFS) to traverse each connected component of the graph, coloring them using two colors to detect any bipartite incompatibility.
  3. Component Analysis and Depth Calculation: For each bipartite connected component, use Breadth-First Search (BFS) to calculate the maximum depth of the BFS tree rooted at each node. This maximum depth will correspond to the number of groups that can be formed within the component.
  4. Combination of Results: Sum the maximum depths (each providing a valid group count) across all connected components to get the total maximum group count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

class Solution {
    public int magnificentSets(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0] - 1).add(e[1] - 1);
            adj.get(e[1] - 1).add(e[0] - 1);
        }

        int[] color = new int[n];
        Arrays.fill(color, -1);
        List<List<Integer>> components = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (color[i] == -1) {
                List<Integer> comp = new ArrayList<>();
                components.add(comp);
                if (!dfs(i, 0, adj, color, comp)) {
                    return -1;
                }
            }
        }

        int maxGroups = 0;
        for (List<Integer> comp : components) {
            maxGroups += bfsMaxDepth(comp, adj);
        }

        return maxGroups;
    }

    private boolean dfs(int node, int col, List<List<Integer>> adj, int[] color, List<Integer> comp) {
        color[node] = col;
        comp.add(node);
        for (int neighbor : adj.get(node)) {
            if (color[neighbor] == col) return false;
            if (color[neighbor] == -1 && !dfs(neighbor, 1 - col, adj, color, comp)) return false;
        }
        return true;
    }

    private int bfsMaxDepth(List<Integer> comp, List<List<Integer>> adj) {
        int maxDepth = 0;
        for (int start : comp) {
            int[] depth = new int[adj.size()];
            Arrays.fill(depth, -1);
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start);
            depth[start] = 0;
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int neighbor : adj.get(node)) {
                    if (depth[neighbor] == -1) {
                        depth[neighbor] = depth[node] + 1;
                        queue.offer(neighbor);
                    }
                }
            }
            maxDepth = Math.max(maxDepth, Arrays.stream(depth).max().getAsInt());
        }
        return maxDepth + 1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        adj = defaultdict(list)
        for u, v in edges:
            adj[u-1].append(v-1)
            adj[v-1].append(u-1)

        color = [-1] * n
        components: List[List[int]] = []
        for i in range(n):
            if color[i] == -1:
                comp = []
                components.append(comp)
                if not self.dfs(i, 0, adj, color, comp):
                    return -1

        max_groups = 0
        for comp in components:
            max_groups += self.bfsMaxDepth(comp, adj)

        return max_groups

    def dfs(self, node: int, col: int, adj: Dict[int, List[int]], color: List[int], comp: List[int]) -> bool:
        color[node] = col
        comp.append(node)
        for neighbor in adj[node]:
            if color[neighbor] == col:
                return False
            if color[neighbor] == -1 and not self.dfs(neighbor, 1 - col, adj, color, comp):
                return False
        return True

    def bfsMaxDepth(self, comp: List[int], adj: Dict[int, List[int]]) -> int:
        max_depth = 0
        for start in comp:
            depth = [-1] * len(adj)
            depth[start] = 0
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for neighbor in adj[node]:
                    if depth[neighbor] == -1:
                        depth[neighbor] = depth[node] + 1
                        queue.append(neighbor)
            max_depth = max(max_depth, max(depth))
        return max_depth + 1

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)