// C++ program to find out whether a given graph can be // converted to two Cliques or not. #include 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 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

what is a clique

Related code examples

Code examples by languages