Two_clique_problem.cpp

// This code is contributed by Avinash Prasad (GitHub : avinash11a)
// C++ program to find out whether a given graph can be 
// converted to two Cliques or not. 
#include <bits/stdc++.h> 
using namespace std; 

const int V = 5; 

// This function returns true if subgraph reachable from 
// src is Bipartite or not. 
bool isBipartiteUtil(int G[][V], int src, int colorArr[]) 
{ 
	colorArr[src] = 1; 

	// Create a queue (FIFO) of vertex numbers and enqueue 
	// source vertex for BFS traversal 
	queue <int> q; 
	q.push(src); 

	// Run while there are vertices in queue (Similar to BFS) 
	while (!q.empty()) 
	{ 
		// Dequeue a vertex from queue 
		int u = q.front(); 
		q.pop(); 

		// Find all non-colored adjacent vertices 
		for (int v = 0; v < V; ++v) 
		{ 
			// An edge from u to v exists and destination 
			// v is not colored 
			if (G[u][v] && colorArr[v] == -1) 
			{ 
				// Assign alternate color to this adjacent 
				// v of u 
				colorArr[v] = 1 - colorArr[u]; 
				q.push(v); 
			} 

			// An edge from u to v exists and destination 
			// v is colored with same color as u 
			else if (G[u][v] && colorArr[v] == colorArr[u]) 
				return false; 
		} 
	} 

	// If we reach here, then all adjacent vertices can 
	// be colored with alternate color 
	return true; 
} 

// Returns true if a Graph G[][] is Bipartite or not. Note 
// that G may not be connected. 
bool isBipartite(int G[][V]) 
{ 
	// Create a color array to store colors assigned 
	// to all veritces. Vertex number is used as index in 
	// this array. The value '-1' of colorArr[i] 
	// is used to indicate that no color is assigned to 
	// vertex 'i'. The value 1 is used to indicate first 
	// color is assigned and value 0 indicates 
	// second color is assigned. 
	int colorArr[V]; 
	for (int i = 0; i < V; ++i) 
		colorArr[i] = -1; 

	// One by one check all not yet colored vertices. 
	for (int i = 0; i < V; i++) 
		if (colorArr[i] == -1) 
			if (isBipartiteUtil(G, i, colorArr) == false) 
				return false; 

	return true; 
} 

// Returns true if G can be divided into 
// two Cliques, else false. 
bool canBeDividedinTwoCliques(int G[][V]) 
{ 
	// Find complement of G[][] 
	// All values are complemented except 
	// diagonal ones 
	int GC[V][V]; 
	for (int i=0; i<V; i++) 
		for (int j=0; j<V; j++) 
			GC[i][j] = (i != j)? !G[i][j] : 0; 

	// Return true if complement is Bipartite 
	// else false. 
	return isBipartite(GC); 
} 

// Driver program to test above function 
int main() 
{ 
	int G[][V] = {{0, 1, 1, 1, 0}, 
		{1, 0, 1, 0, 0}, 
		{1, 1, 0, 0, 0}, 
		{0, 1, 0, 0, 1}, 
		{0, 0, 0, 1, 0} 
	}; 

	canBeDividedinTwoCliques(G) ? cout << "Yes" : 
								cout << "No"; 
	return 0; 
}