Is Graph Bipartite?

Problem Id: 785 Difficulty: Medium


Intuition

Solution


class Solution:
    def isBipartite(self, adj: List[List[int]]) -> bool:
        n = len(adj)
        self.bipartite = True
        self.color = [False] * n
        self.visited = [False] * n

        for i in range(n):
            if not self.visited[i]:
                self.dfs(adj, i)
        return self.bipartite

    def dfs(self, adj, vertex):
        self.visited[vertex] = True
        for child in adj[vertex]:
            if not self.visited[child]:
                self.color[child] = not self.color[vertex]
                self.dfs(adj, child)
            elif self.color[child] == self.color[vertex]:
                self.bipartite = False