Is Graph Bipartite? | Leetcode 785 | Easy 2-Color DFS Solution in Python

Learn how to test if an undirected graph is bipartite by coloring it with two colors. Simple DFS idea, commented Python code, dry run, and Big-O analysis.

Here’s the [Problem Link] to begin with.

What does the problem ask?

You get an undirected graph as an adjacency list graph.
Your job is to say true if you can color every node using only two colors such that no two connected nodes share the same color.
If this is impossible, return false.

Examples

Intuition & Approach

1. Think in colors.
   Bipartite means we can split nodes into two groups (colors). Adjacent nodes must land in different groups.
2. Pick a start node → give it color 0.
   Then travel through its neighbors with DFS.
3. Color neighbors with the opposite color (1 − current).
   • If a neighbor already has a color and it matches ours, we found a clash → graph is not bipartite.
4. Handle disconnected parts.
   The graph may have many separate components, so repeat the DFS for every still-uncolored node.
5. If no clashes appear, the graph is bipartite.

Code

class Solution:
    # Helper DFS to try coloring one component
    def dfs(self, current_node, visited, graph, color):
        visited[current_node] = color          # paint current node
        for adjNode in graph[current_node]:    # go through all neighbors
            if visited[adjNode] != -1:         # neighbor already colored
                if visited[adjNode] == color:  # same color → clash!
                    return False
            else:
                # color neighbor with opposite color (1 - color)
                ans = self.dfs(adjNode, visited, graph, 1 - color)
                if ans == False:               # clash found deeper
                    return False
        return True                            # this branch is fine

    def isBipartite(self, graph: List[List[int]]) -> bool:
        total_nodes = len(graph)
        visited = [-1] * total_nodes           # -1 means "no color yet"
        for index in range(0, total_nodes):
            if visited[index] == -1:           # unvisited component
                ans = self.dfs(index, visited, graph, 0)  # start with color 0
                if ans == False:               # clash in this component
                    return False
        return True                            # all components are okay

Code explanation (step-by-step)

1. visited array
   Size = number of nodes
   • -1 → not colored yet
   • 0 or 1 → the chosen color
2. Main loop goes through every node:
   • If the node is not colored, we launch DFS from it.
3. DFS routine
   • Colors current node.
   • Checks all neighbors:
     • If neighbor has same color → immediately return False.
     • If neighbor is uncolored → recursively color it with 1 - color.
   • If recursion finishes with no clashes → return True.
4. If any component returns False, the full graph is not bipartite.
   Otherwise return True.

Dry run on the first example

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

Complexity

Explanation

• We touch every vertex and every edge once during DFS.
• visited array and recursion stack need up to V entries.

Conclusion

A graph is bipartite if you can 2-color it with no clashes.
Depth-First Search plus an array that stores each node’s color is a quick and clear way to test this. If a conflict appears at any step, we know right away the graph needs more than two colors; otherwise it is bipartite.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.