0886 Possible Bipartition

0886 Possible Bipartition#

Problem#

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] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Examples#

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

Constraints:#

1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= ai < bi <= n
All the pairs of dislikes are unique.

Analysis

  • we can maintain two global set to track visited nodes and their colors

  • the graph might not be connected. We cannot use indegree to check the starting vertex like in a DAG for this undirected graph.

    • thus we need a for loop to enable the traversal algorithms, i.e., BFS, DFS

  • BFS

    • the queue only stores nodes that have not been visited/colored yet

# BFS 1: use a global variable to store the result
def possibleBipartition(N, dislikes):
    # construct an undirected graph
    graph = {}
    for i in range(1, N+1):
        graph[i] = []
    for u, v in dislikes:
        graph[u].append(v)
        graph[v].append(u)
    
    # color the graph using BFS
    colors = {}
    visited = set()

    # define result
    bipartition = True 

    def bfs(graph, u):
        nonlocal bipartition
        # if u is not visited, visit it and color it
        # else do nothing and exit
        if u not in visited:
            visited.add(u)
            colors[u] = 0

            queue = [u]

            while queue:
                u = queue.pop(0)
                # color the neighbors of u
                for v in graph[u]:
                    # if v is not visited, visit, color and enqueue
                    if v not in visited:
                        visited.add(v)
                        colors[v] = 1 - colors[u]
                        queue.append(v)
                    else:
                        # if v is visited, check if the colors are different
                        if colors[v] == colors[u]:
                            bipartition = False
                            return
    # examine all nodes
    for u in graph:
        bfs(graph, u)
    return bipartition

# test
N = 4
dislikes = [[1,2],[1,3],[2,4]]
print(possibleBipartition(N, dislikes))

N = 3
dislikes = [[1,2],[1,3],[2,3]]
print(possibleBipartition(N, dislikes))

True
False

# BFS 2: use a local variable to store the result
def possibleBipartition(N, dislikes):
    # construct an undirected graph
    graph = {}
    for i in range(1, N+1):
        graph[i] = []
    for u, v in dislikes:
        graph[u].append(v)
        graph[v].append(u)
    
    # color the graph using BFS
    colors = {}
    visited = set()

    # bfs return if a graph is bipartition
    def bfs(graph, u):
        # if u is not visited, visit it and color it
        # else do nothing and exit
        if u not in visited:
            visited.add(u)
            colors[u] = 0

            queue = [u]

            while queue:
                u = queue.pop(0)
                # color the neighbors of u
                for v in graph[u]:
                    # if v is not visited, visit, color and enqueue
                    if v not in visited:
                        visited.add(v)
                        colors[v] = 1 - colors[u]
                        queue.append(v)
                    else:
                        # if v is visited, check if the colors are different
                        if colors[v] == colors[u]:
                            return False 
        return True 
    # examine all nodes
    for u in graph:
        if not bfs(graph, u):
            return False 

    return True

# test
N = 4
dislikes = [[1,2],[1,3],[2,4]]
print(possibleBipartition(N, dislikes))

N = 3
dislikes = [[1,2],[1,3],[2,3]]
print(possibleBipartition(N, dislikes))

True
False

# DFS
def possibleBipartition(N, dislikes):
    # construct an undirected graph
    graph = {}
    for i in range(1, N+1):
        graph[i] = []
    for u, v in dislikes:
        graph[u].append(v)
        graph[v].append(u)
    
    # color the graph using DFS
    colors = {}
    visited = set()

    # dfs traverse the graph and return if a graph is bipartition
    def dfs(graph, u, color):
        
        visited.add(u)
        colors[u] = color

        for v in graph[u]:
            if v not in visited:
                dfs(graph, v, 1-color)
            else:
                if colors[v] == colors[u]:
                    return False
        return True
        
    # examine all nodes
    for u in graph:
        colors[u] = 0 if u not in colors else colors[u]

        if not dfs(graph, u, colors[u]):
            return False
    return True

# test
N = 4
dislikes = [[1,2],[1,3],[2,4]]
print(possibleBipartition(N, dislikes))

N = 3
dislikes = [[1,2],[1,3],[2,3]]
print(possibleBipartition(N, dislikes))

True
False
Contents