The code below is returning true
for connected bipartite graphs but false
for unconnected bipartite graphs. It's failing the test case for graph [[1,3],[0,2],[1,3],[0,2]]
.
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> visited(n, 0); // Using a vector for visited instead of an array
for (int j = 0; j < n; j++) {
if (visited[j] == 0) { // If the current node is unvisited
if (bfsTraversal(graph, j, visited) == false) {
return false;
}
}
}
return true;
}
bool bfsTraversal(vector<vector<int>>& graph, int startNode, vector<int>& visited) {
queue<pair<int, int>> bfs;
bfs.push(make_pair(startNode, 1));
visited[startNode] = 1;
while (!bfs.empty()) {
int row_num = bfs.front().first;
int color = bfs.front().second;
bfs.pop();
for (int i = 0; i < graph[row_num].size(); i++) {
if (graph[row_num][i] == 1) {
if (visited[i] == color) {
return false;
}
if (visited[i] == 0) {
visited[i] = -color;
bfs.push(make_pair(i, -color));
}
}
}
}
return true;
}
};
So I have used a queue in which I am storing the node and its corresponding color which and a visited vector to store the color of each node on bfs traversal. I am coloring nodes differently which are adjacent to each other and nodes which are not colored are denoted as 0 in visited vector. I'm using two colors denoted as -1 and 1. The code is giving correct result for connected graph but not so in the case of unconnected graph.