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

Possible Bipartition

Difficulty: Medium

Problem Description

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group. Given the integer n and the array dislikes where dislikes[i] = [a_i, b_i] indicates that the person labeled a_i does not like the person labeled b_i, return true if it is possible to split everyone into two groups in this way.

Key Insights

  • The problem can be viewed as a graph bipartitioning problem where the people are nodes and dislikes are edges.
  • If we can color the graph using two colors (representing the two groups) without conflicts, then a valid partitioning exists.
  • Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to traverse the graph and attempt to color it.
  • If at any point we find a node that needs to be colored the same as one of its adjacent nodes, then a bipartition is impossible.

Space and Time Complexity

Time Complexity: O(n + e), where n is the number of people and e is the number of dislikes (edges). Space Complexity: O(n), for storing the graph and the color assignments.

Solution

To solve this problem, we can utilize a graph representation where each person is a node and each dislike relationship is an edge. Using either Depth-First Search (DFS) or Breadth-First Search (BFS), we'll attempt to color the graph using two colors. If we encounter an adjacent node that is already colored with the same color as the current node, we cannot proceed with the bipartition.

  1. Construct the graph using an adjacency list.
  2. Initialize a color array to track the color assigned to each node.
  3. For each unvisited node, perform a DFS/BFS:
    • Assign a color to the current node.
    • For each of its neighbors, if they are uncolored, assign them the opposite color and continue the search.
    • If a neighbor is already colored and has the same color as the current node, return false.
  4. If all nodes are processed without conflicts, return true.

Code Solutions

def possibleBipartition(n, dislikes):
    from collections import defaultdict, deque
    
    # Step 1: Create the graph
    graph = defaultdict(list)
    for a, b in dislikes:
        graph[a].append(b)
        graph[b].append(a)
    
    # Step 2: Initialize color array
    color = [0] * (n + 1)

    # Step 3: Define a BFS function
    def bfs(start):
        queue = deque([start])
        color[start] = 1  # Start coloring with 1
        
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if color[neighbor] == 0:  # Not colored
                    color[neighbor] = -color[node]  # Assign opposite color
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:  # Conflict
                    return False
        return True

    # Step 4: Try to color all components
    for person in range(1, n + 1):
        if color[person] == 0:  # Unvisited
            if not bfs(person):
                return False

    return True
← Back to All Questions