We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Divide Nodes Into the Maximum Number of Groups

Difficulty: Hard

Problem Description

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. Divide the nodes of the graph into m groups (1-indexed) such that each node in the graph belongs to exactly one group, and 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.

Key Insights

  • The problem requires dividing nodes of a graph into groups such that connected nodes are placed in adjacent groups.
  • The graph can be disconnected, meaning we may need to consider each connected component separately.
  • If any component has an odd cycle, it will be impossible to satisfy the grouping condition, hence the return value should be -1 for that component.
  • A valid grouping can be achieved by performing a bipartite check using BFS or DFS.

Space and Time Complexity

Time Complexity: O(n + edges.length) - where n is the number of nodes and edges.length is the number of edges. Each node and edge is processed once. Space Complexity: O(n) - for storing the graph as an adjacency list and for the visited array.

Solution

To solve the problem, we can treat the graph as a bipartite graph. We will use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and attempt to color the graph using two colors (representing two groups). If we find a conflict while trying to color the graph (i.e., adjacent nodes having the same color), we return -1. The maximum number of groups can then be determined by the number of colors used.

Code Solutions

def maxGroups(n, edges):
    from collections import defaultdict, deque

    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    def bfs(start):
        queue = deque([start])
        color[start] = 0
        count = 1
        
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    count += 1
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return -1
        return count

    color = [-1] * (n + 1)
    total_groups = 0
    
    for i in range(1, n + 1):
        if color[i] == -1:
            count = bfs(i)
            if count == -1:
                return -1
            total_groups += 1
    
    return total_groups * 2

# Example usage
print(maxGroups(6, [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]))  # Output: 4
print(maxGroups(3, [[1,2],[2,3],[3,1]]))  # Output: -1
← Back to All Questions