Solution
This is a pretty standard question for determining whether a given graph is bipartite. A bipartite graph can be colored using two colors, say red and green, where no two adjacent nodes have the same color. Consider a graph coloring below:
Graph:
0----1
| |
| |
3----2
Coloring:
0: red
1: green
2: red
3: green
This ensures that no two adjacent nodes have the same color.
Knowing this, check for bipartite graph is simple. We apply standard DFS and start with a root node, say 0. We color 0 as red (represented by integer 1) and then color all its adjacent nodes with green (represented by integer 0) and then perform a DFS on adjacent nodes. Below is a iterative solution for the same. Please note that the graph can be disconnected as well so you have to take care of it.
bool isBipartite(vector<vector<int>>& graph) {
// snaity check
if (graph.size() == 0)
return true;
// this stores colors of nodes and also works as a visited array. If color[node] = -1 then it is not visited yet
vector<int> color(graph.size(), -1);
stack<int> s;
// graph maybe disconnected so visit each node
for (int i=0; i<graph.size(); i++) {
// if node is visited, continue
if (color[i] != -1)
continue;
// color node as red
color[i] = 1;
s.push(i);
while (!s.empty()) {
int t = s.top();
s.pop();
for (int x : graph[t]) {
// if adjacent node has same color, graph is not bipartite
if (color[x] != -1 && color[x]==color[t])
return false;
// color adjacent nodes with different color if it is not visited
if (color[x] == -1) {
color[x] = color[t] == 1 ? 0 : 1;
s.push(x);
}
}
}
}
return true;
}
Time complexity: O(n) where n is the number of nodes