C++ Bipartite Graph(Graph Coloring Method) using BFS


#1

int Solution::solve(int A, vector<vector > &B) {
int m = B.size();
int n = B[0].size();
vector edges[A+1];
for(int i=0;i<m;i++){
edges[B[i][0]].push_back(B[i][1]);
edges[B[i][1]].push_back(B[i][0]);
}
queue pendingNodes;
int *colors = new int[A+1];
colors[0] = -1;
colors[1] = 1;
for(int i=2;i<=A;i++) colors[i] = -1;
pendingNodes.push(1);
while(!pendingNodes.empty()){
int vertex = pendingNodes.front();
pendingNodes.pop();
int assignedColor = colors[vertex];
for(int i=0;i<edges[vertex].size();i++){
int currVertex = edges[vertex][i];
int colorToThisVertex = colors[currVertex];
if(colorToThisVertex == -1){
colors[currVertex] = 1 - assignedColor;
pendingNodes.push(currVertex);
}else{
if(colorToThisVertex == assignedColor) return 0;
}
}
}
return 1;
}