Bipartite Graph - DFS

A graph is said to be bipartite if it can be colored using two colors such that no two adjacent nodes have same color.

Graph should be undirected.

Practice Link

Sample 1#

output: BIPARTITE

Sample 2#

output: NOT BIPARTITE

Observations#

• Any linear graph with no cycle - always bipartite
• With Cycle
  1. Even Cycle Length - Bipartite
  2. odd cycle length - can NEVER be bipartite

Note#

Carefully handle the disconnected components.

DFS#

The DFS approach to bipartite checking propagates colors depth-first rather than level-by-level. Each recursive call passes the intended color for the next node — the opposite of the current node's color. If a neighbor is already colored the same as the current node, there is a conflict and the graph is not bipartite. DFS explores the entire connected component before returning, making it easy to validate each edge constraint along every path.

Instead of a queue, call the DFS method recursively and pass the color to assign to the next node.

Two cases possible:

1. color[adj_node] == -1 → not yet visited; recurse with the opposite color (1 - color); if that subtree fails, propagate false.
2. color[adj_node] == color[current_node] → same color conflict → not bipartite; return false.

Implementation#

class Solution {
public:
    bool checkBipartiteDFS(vector<vector<int>>& graph, vector<int> &colors, int node, int color)
    {
        colors[node] = color;

        for(int next: graph[node])
        {
            if(colors[next] == -1 && !checkBipartiteDFS(graph, colors, next, 1-color))
                return false;
            else if(colors[next]==color)
                return false;
        }
        return true;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int V  = graph.size();
        vector<int> colors(V, -1);

        for(int i=0;i<V;i++)
        {
            if(colors[i] == -1 && !checkBipartiteDFS(graph, colors, i, 0))
                return false;
        }
        return true;
    }
};

Complexities#

Time Complexity: O(N*(V+E)) -> to cover all disconnected components