Is Graph Bipartite?
Medium · Graphs · Explanation and code example
Disjoint Set Union
How it works
DSU (Union-Find) offers an alternative perspective. For a bipartite graph, a node must be in a different set than all of its neighbors, but all neighbors should belong to the same set. For each node, we union all its neighbors together. If a node ever ends up in the same set as one of its neighbors, the graph is not bipartite. This works because being in the same connected component in the neighbor graph implies they must share a color in a valid 2-coloring.
Steps
- Initialize a DSU structure with
nnodes. - For each node:
- If it has no neighbors, continue.
- For each neighbor:
- If the node and neighbor are in the same set, return
false. - Union the neighbor with the first neighbor of the current node (grouping all neighbors together).
- If the node and neighbor are in the same set, return
- Return
trueif no conflict is detected.
Complexity
- Time complexity:
O(V + (E * α(V))) - Space complexity:
O(V)
Where
Vis the number of vertices andEis the number of edges.α()is used for amortized complexity.
Things to watch for
Forgetting to Handle Disconnected Components
The graph may consist of multiple disconnected components. If you only run BFS/DFS from node 0, you will miss other components that might not be bipartite. Always iterate through all nodes and start a new traversal from any unvisited node to ensure every component is checked.
Checking Only Unvisited Neighbors
When traversing the graph, you must check the color of all neighbors, not just unvisited ones. If a neighbor is already colored with the same color as the current node, the graph is not bipartite. Skipping already-visited neighbors misses these conflict cases.
Using Wrong Initial Color Values
Using 0 as a valid color while also using it to represent "unvisited" creates ambiguity. A clean approach is to use 0 for unvisited nodes and 1/-1 as the two actual colors. Alternatively, use a separate visited array. Mixing up these states leads to incorrect bipartiteness detection.
Python code example
from typing import List
class DSU:
def __init__(self, n):
self.Parent = list(range(n))
self.Size = [0] * n
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu, pv = self.find(u), self.find(v)
if pu == pv:
return False
if self.Size[pu] > self.Size[pv]:
self.Parent[pv] = pu
elif self.Size[pu] < self.Size[pv]:
self.Parent[pu] = pv
else:
self.Parent[pv] = pu
self.Size[pu] += 1
return True
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
dsu = DSU(n)
for node in range(n):
for nei in graph[node]:
if dsu.find(node) == dsu.find(nei):
return False
dsu.union(graph[node][0], nei)
return True
C++ code example
class DSU {
private:
vector<int> Parent, Size;
public:
DSU(int n) {
Parent.resize(n);
Size.resize(n, 0);
for (int i = 0; i < n; i++) {
Parent[i] = i;
}
}
int find(int node) {
if (Parent[node] != node) {
Parent[node] = find(Parent[node]);
}
return Parent[node];
}
bool unionSet(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] > Size[pv]) {
Parent[pv] = pu;
} else if (Size[pu] < Size[pv]) {
Parent[pu] = pv;
} else {
Parent[pv] = pu;
Size[pu]++;
}
return true;
}
};
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
DSU dsu(n);
for (int node = 0; node < n; node++) {
for (int& nei : graph[node]) {
if (dsu.find(node) == dsu.find(nei)) {
return false;
}
dsu.unionSet(graph[node][0], nei);
}
}
return true;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.