Is Graph Bipartite? — LeetCode 785 Python Solution

The problem

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to.

Example

Input

graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output

false

Explanation

There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Python solution

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(a: int, c: int) -> bool:
            color[a] = c
            for b in graph[a]:
                if color[b] == c or (color[b] == 0 and not dfs(b, -c)):
                    return False
            return True

        n = len(graph)
        color = [0] * n
        for i in range(n):
            if color[i] == 0 and not dfs(i, 1):
                return False
        return True

Complexity

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 785. Is Graph Bipartite? is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems