Problem statement

https://binarysearch.com/problems/Bipartite-Graph/

Solution

Equal to Leetcode 0785. Is Graph Bipartite

Complexity

Time complexity is O(E+V), because it is complexity of classical dfs we are using. Space complexity is O(V) to keep dist array. Here E is number of edges and V is number of vertices.

Code

class Solution:
    def solve(self, graph):
        def dfs(start):
            if self.loop: return

            for neib in graph[start]:
                if dist[neib] >= 0 and dist[neib] == dist[start]:
                    self.loop = True
                elif dist[neib] < 0:
                    dist[neib] = dist[start]^1
                    dfs(neib)
            
        n = len(graph) 
        self.loop, dist = 0, [-1] *(n)
        
        for i in range(n):
            if self.loop: return False
            if dist[i] == -1:
                dist[i] = 0
                dfs(i)
                
        return True