-4

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.

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
Asha
  • 1
  • 3
  • "given adjacency matrix" but [[1,3],[0,2],[1,3],[0,2]]. is not an adjacency matrix. – ravenspoint Aug 28 '23 at 20:13
  • "unconnected bipartite graphs" what would this exotic creature look like? If a graph is not connected, how could it be bipartite? – ravenspoint Aug 28 '23 at 20:16
  • *The code is giving correct result for connected graph but not so in the case of unconnected graph.* -- [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – PaulMcKenzie Aug 28 '23 at 21:05
  • No question asked. – Evg Aug 28 '23 at 21:49
  • @ravenspoint [It could look like this](https://math.stackexchange.com/questions/1042738/bipartite-graph-and-non-connected-node). – Nelfeal Aug 28 '23 at 22:49
  • OK, if you want to define a bipartite graph that way ( you will be in a small minority ) then 1) remove all nodes that have zero connections 2) Determine if remaining graph is bipartite 3) Add the the unconnected nodes back and declare the graph bipartite ( by your definition. ) – ravenspoint Aug 29 '23 at 00:08

0 Answers0