Is Graph Bipartite? - Practice Coding Problems

Is Graph Bipartite? - Problem

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to.

More formally, for each v in graph[u], there is an undirected edge between node u and node v.

The graph has the following properties:

There are no self-edges (graph[u] does not contain u)
There are no parallel edges (graph[u] does not contain duplicate values)
If v is in graph[u], then u is in graph[v] (the graph is undirected)
The graph may not be connected

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Input & Output

Example 1 — Simple Bipartite Graph

$ Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

› Output: false

💡 Note: This forms a 4-cycle: 0-1-2-3-0. Since it's an even cycle, we expect it to be bipartite, but let's trace: if we color 0 as blue, then 1,2,3 must be red. But 1 and 2 are connected, so both can't be red. Actually this is not bipartite due to the triangle 0-1-2-0.

Example 2 — Tree Structure

$ Input: graph = [[1,3],[0,2],[1,3],[0,2]]

› Output: true

💡 Note: This forms a 4-cycle: 0-1-2-3-0. We can color it as: Set A = {0,2}, Set B = {1,3}. All edges connect different sets, so it's bipartite.

Example 3 — Odd Cycle

$ Input: graph = [[1,2],[0,2],[0,1]]

› Output: false

💡 Note: This is a triangle (3-cycle). Triangles are odd cycles and cannot be bipartite. If we color 0 as blue, then 1 and 2 must be red, but 1 and 2 are connected.

Constraints

1 ≤ graph.length ≤ 100
0 ≤ graph[u].length < graph.length
0 ≤ graph[u][i] ≤ graph.length - 1
graph[u] does not contain u
All the values of graph[u] are unique
If graph[u] contains v, then graph[v] contains u

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Adjacency list representation of undirected graph

Color Assignment

Try to color nodes with two colors alternately

Bipartite Check

Verify no adjacent nodes have same color

Key Takeaway

🎯 Key Insight: A graph is bipartite if and only if it contains no odd-length cycles

Asked in

G Google 15 a Amazon 12 M Microsoft 10 f Facebook 8

The key insight is that a graph is bipartite if and only if it contains no odd-length cycles. Best approach is DFS/BFS graph coloring - try to color the graph with two colors such that no adjacent nodes have the same color. Time: O(V + E), Space: O(V)

Common Approaches

Approach	Time	Space	Notes
✓ DFS Graph Coloring	O(V + E)	O(V)	Use DFS to color nodes with alternating colors (0 and 1)
BFS Graph Coloring	O(V + E)	O(V)	Use BFS to color nodes level by level with alternating colors
Brute Force - Try All Partitions	O(n × 2ⁿ)	O(n)	Generate all possible ways to partition nodes into two sets

DFS Graph Coloring — Algorithm Steps

Initialize color array with -1 (uncolored)
For each uncolored node, start DFS with color 0
In DFS, color neighbors with opposite color
If neighbor already has same color, return false

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin with node 0, color it with 0

Color Neighbors

Color adjacent nodes with opposite color 1

Check Conflicts

If neighbor has same color, not bipartite

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool dfs(int** graph, int* graphSizes, int* color, int node, int c) {
    color[node] = c;
    for (int i = 0; i < graphSizes[node]; i++) {
        int neighbor = graph[node][i];
        if (color[neighbor] == c) { // Same color conflict
            return false;
        }
        if (color[neighbor] == -1 && !dfs(graph, graphSizes, color, neighbor, 1 - c)) {
            return false;
        }
    }
    return true;
}

bool solution(int** graph, int* graphSizes, int graphSize) {
    int* color = (int*)malloc(graphSize * sizeof(int));
    for (int i = 0; i < graphSize; i++) {
        color[i] = -1; // -1: uncolored, 0: color A, 1: color B
    }
    
    // Check all components
    for (int i = 0; i < graphSize; i++) {
        if (color[i] == -1) {
            if (!dfs(graph, graphSizes, color, i, 0)) {
                free(color);
                return false;
            }
        }
    }
    free(color);
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[1,2],[2,3],[1,3]] format
    int graph[100][100];
    int graphSizes[100];
    int graphSize = 0;
    
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            graphSizes[graphSize] = 0;
            while (*ptr != ']') {
                int num = 0;
                while (*ptr >= '0' && *ptr <= '9') {
                    num = num * 10 + (*ptr - '0');
                    ptr++;
                }
                graph[graphSize][graphSizes[graphSize]++] = num;
                if (*ptr == ',') ptr++;
            }
            ptr++; // Skip ]
            graphSize++;
        }
        if (*ptr == ',') ptr++;
    }
    
    int* graphPtrs[100];
    for (int i = 0; i < graphSize; i++) {
        graphPtrs[i] = graph[i];
    }
    
    printf(solution(graphPtrs, graphSizes, graphSize) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Visit each vertex once and each edge once during DFS traversal

✓ Linear Growth

Space Complexity

O(V)

Color array of size V plus recursion stack depth up to V

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Graph Coloring — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler