Bipartition

886. Possible Bipartition

For this problem, if we simulate the coloring process to see whether we have conflicts during generating a two-color graph.
Using BFS/DFS we can generate multiple subgraphs. If any of the subgraphs have conflict, return False. If not, we may have more than one subgraph,
It is easy to show that if we flip the color of a Bipartition graph, it is still a Bipartition graph. Base on this, we can combine them into one big Bipartition graph by connecting different subgraphs and flipping the color if needed.

If we have a final big Bipartition graph, we divide the whole nodes into two groups corresponding to those two colors.

https://leetcode.com/contest/weekly-contest-97/problems/possible-bipartition/

https://leetcode.com/problems/possible-bipartition/discuss/160371/Python-Decide-if-a-graph-is-bipartite-by-checking-the-existence-of-odd-cycles.

DFS (756ms)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def good(i):
            open_list = [(i, 1)]
            while open_list:
                i, color = open_list.pop()
                if i in colors:
                    # color does not match
                    if colors[i] != color:return False
                # coloring this node and the children nodes of this node
                else:
                    colors[i] = color
                    for v in connections[i]:
                        open_list.append((v, -color))
            return True
        connections = collections.defaultdict(list)
        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)
        colors = {}
        for i in range(1, N+1):
            if i not in colors and not good(i):return False
        return True

DFS2 (748ms)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(i):
            open_list = [i]
            colors[i] = 1
            while open_list:
                i = open_list.pop()
                for v in connections[i]:
                    if v in colors:
                        if colors[v] != -colors[i]:return False
                    else:
                        colors[v] = -colors[i]
                        open_list.append(v)
            return True
        connections = collections.defaultdict(list)
        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)
        colors = {}
        for i in range(1, N+1):
            if i not in colors and not dfs(i):return False
        return True

BFS (752ms)

from collections import deque
class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def bfs(i):
            que = deque([i])
            colors[i] = 1
            while que:
                i = que.popleft()
                for v in connections[i]:
                    if v in colors:
                        if colors[v] != -colors[i]:return False
                    else:
                        colors[v] = -colors[i]
                        que.append(v)
            return True
        connections = collections.defaultdict(list)
        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)
        colors = {}
        for i in range(1, N+1):
            if i not in colors and not bfs(i):return False
        return True

DFS by recursion (796ms)

class Solution:
    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
        def dfs(i, color):
            if i in colors:return colors[i] == color
            colors[i] = color
            return all(dfs(v, -color) for v in connections[i])
        
        connections, colors = collections.defaultdict(list), {}
        for a, b in dislikes:
            connections[a].append(b)
            connections[b].append(a)
        for i in range(1, N+1):
            if i not in colors and not dfs(i, 1):return False
        return True

This problem is similar to

785. Is Graph Bipartite

Also, it has some similarity to the problem

882. Reachable Nodes In Subdivided Graph

https://medium.com/@jim.morris.shen/hard-graph-f7a92d9f1def?source=friends_link&sk=196bdc5a29dd0272b8ac2e77741b496a