#785 Is Graph Bipartite? - Solution

Dashboard Questions Topics Companies Sheets

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, meaning there may be two nodes u and v such that there is no path between them.

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.

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints:

graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 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.

Approach	Time Complexity	Space Complexity
BFS / DFS Graph Coloring	O(V + E)	O(V)
Union-Find	O(E α(V))	O(V)

Solutions (12)

Two-Coloring/BFS Approach

This approach uses breadth-first search (BFS) to try and color the graph using two colors, validating its bipartiteness. By starting at any unvisited node and attempting to color it with one color, you color all its neighbors with an alternating color. If at any point a neighbor is found to already have the same color, then the graph cannot be bipartite.

The time complexity is O(V + E) where V is the number of vertices and E is the number of edges, as each edge and vertex is visited once in BFS. The space complexity is O(V) due to the storage needed for the color array and the BFS queue.

C C++Java Python C#JavaScript

1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6bool bfsCheck(int start, vector<vector<int>>& graph, vector<int>& colors) {
7    queue<int> q;
8    q.push(start);
9    colors[start] = 0;
10    
11    while (!q.empty()) {
12        int node = q.front();
13        q.pop();
14
        for (int neighbor : graph[node]) {
            if (colors[neighbor] == -1) {
                colors[neighbor] = 1 - colors[node];
                q.push(neighbor);
            } else if (colors[neighbor] == colors[node]) {
                return false;
            }
        }
    }
    return true;
}

bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> colors(n, -1);
    
    for (int i = 0; i < n; ++i) {
        if (colors[i] == -1) {
            if (!bfsCheck(i, graph, colors)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<int>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
    cout << (isBipartite(graph) ? "true" : "false") << endl;
    return 0;
}

Explanation

In this C++ implementation, the graph is represented using an adjacency list (vector of vectors). The bfsCheck function is responsible for conducting a BFS on unvisited nodes, trying to color adjacent nodes with alternating colors. A same-color conflict during the traversal indicates the graph is non-bipartite.

DFS Approach

The depth-first search (DFS) approach is an alternative to BFS for examining bipartiteness. You use DFS recursively to color the graph and check for conflicts. The method still involves checking whether adjacent nodes have opposing colors, iterating through components one by one as needed.

The time complexity is O(V + E), and the space complexity is O(V) due to recursive depth stack space utilization.

C C++Java Python C#JavaScript

1
public class BipartiteGraphDFS {
    public bool DfsCheck(int node, int color, int[][] graph, int[] colors) {
        colors[node] = color;

        foreach (int neighbor in graph[node]) {
            if (colors[neighbor] == -1) {
                if (!DfsCheck(neighbor, 1 - color, graph, colors)) return false;
            } else if (colors[neighbor] == colors[node]) {
                return false;
            }
        }
        return true;
    }

    public bool IsBipartite(int[][] graph) {
        int n = graph.Length;
        int[] colors = new int[n];
        Array.Fill(colors, -1);

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

    public static void Main() {
        BipartiteGraphDFS bg = new BipartiteGraphDFS();
        int[][] graph = new int[][] {
            new int[] {1, 3}, new int[] {0, 2},
            new int[] {1, 3}, new int[] {0, 2}
        };
        Console.WriteLine(bg.IsBipartite(graph));
    }
}