Solution: Check If Given Graph is Bipartite

#include "Graph.h"
bool Graph::utilityFunction(int v, vector<bool>& visited, vector<int>& color) { 
	list <int> ::iterator i;
  for (i = adjacencyList[v].begin(); i != adjacencyList[v].end(); ++i) {
		if (visited[*i] == false) { 
			visited[*i] = true; 
			color[*i] = !color[v]; // give different color to adjacent node
			if (this -> utilityFunction(*i, visited, color) == false) // recursion
				return false; 
		} 
		else if (color[*i] == color[v]) // if same color of adjacent node
                                      // then graph is not bipartite
			return false; 
	} 
	return true; 
} 
bool Graph::isBipartite(int source) { 
	vector<bool> visited(this -> vertices); 
	vector<int> color(this -> vertices); 
  
	visited[source] = true; 
	color[source] = 0; 
	if (this -> utilityFunction(source, visited, color)) { 
    return true;
	} 
	else { 
    return false;
	} 
} 
int main() { 
	int V = 6; 
  Graph g(V);
	g.addEdge(0, 1); 
	g.addEdge(1, 2); 
	g.addEdge(2, 3); 
	g.addEdge(3, 4); 
	g.addEdge(4, 5); 
	g.addEdge(5, 0); 
  
  //Example 1
  int source = 0;
  if (g.isBipartite(source)){
    cout << " Graph1 is bipartite" << endl;
  }
  else
    cout << " Graph1 is not bipartite" << endl;
  cout << endl;
  
  
  V = 5; 
  Graph g1(V);
	g1.addEdge(0, 1); 
	g1.addEdge(0, 2); 
	g1.addEdge(0, 3); 
	g1.addEdge(0, 4); 
	g1.addEdge(1, 2); 
  
  //Example 2
  if (g1.isBipartite(source)){
    cout << " Graph2 is bipartite" << endl;
  }
  else
    cout << " Graph2 is not bipartite" << endl;
  cout << endl;
}