Bipartite Graph

"""
Problem:
Given a graph with v vertices and edge list, determine whether the graph
is bipartite. A graph is bipartite if we can divide nodes into two groups
such that no two adjacent nodes belong to the same group.

Intuition:
We treat this as a 2-coloring problem using DFS.
Instead of a visited array, we use a color array:
    -1 → unvisited
     0 → color A
     1 → color B

We assign a color to a node and try to assign the opposite color to all
its neighbors. If at any point a neighbor already has the same color as
the current node, the graph is not bipartite.

This works because a valid bipartite graph can always be colored using
two colors, and any conflict indicates an odd-length cycle.

Steps:
1. Build adjacency list from edges.
2. Initialize color array with -1.
3. Traverse all nodes (to handle disconnected graph):
    - If node is unvisited, start DFS with color 0.
4. In DFS:
    - Assign current color to node.
    - For each neighbor:
        a. If same color → return False.
        b. If unvisited → recursively assign opposite color.
5. If all nodes are processed without conflict → return True.

Time Complexity: O(V + E)
Space Complexity: O(V)
"""
from collections import defaultdict
def dfs(i,cur_color,graph,colors):
    colors[i]=cur_color
    for neigh in graph[i]:
        if colors[neigh]==cur_color:
            return False
        if colors[neigh]==-1:
            if cur_color==0 and not dfs(neigh,1,graph,colors):
                return False
            elif cur_color==1 and not dfs(neigh,0,graph,colors):
                return False
    return True


class Solution:
    def isBipartite(self, v, edges):
        colors=[-1]*v
        graph=defaultdict(list)
        for a,b in edges:
            graph[a].append(b)

        for i in range(v):
            if colors[i]==-1: #not visited
                if dfs(i,0,graph,colors)==False:
                    return False
        return True