Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 🤓
1.1.
Problem Statement 🤔
1.2.
Sample Example 🧐
2.
Complement Graph Approach 🧑‍💻
2.1.
Algorithm 🧑‍💻✨
2.2.
Implementation 🧑‍💻🌝
2.2.1.
Time Complexity ⏳
2.2.2.
Space Complexity 🌌
3.
Frequently Asked Questions 
3.1.
What are Cliques?
3.2.
What is a Bipartite Graph?
3.3.
What is the difference between a clique and a complete graph?
3.4.
What are the most basic terms used in graph theory?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

Check if the Graph can be Divided into Two Cliques

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction 🤓

We are playing with the graphs from the middle school. Making flowcharts, connecting two quantities with lines, and measurements, are all a part of our middle school maths syllabus. But ever wonder how you can implement them in the real world!? Well, as a programmer, you need these tools more than anybody else.

introduction

This article will discuss how to check if the graph can be divided into two cliques. This problem is popularly known as the two cliques problem. A Clique is a subgraph of the graph. Here all the vertices in the subgraph are completely connected. A graph can only be divided into two cliques if their complement is a Bipartite graph.
 

Check if the graph can be divided into two cliques

You should try this problem by yourself before preceding this article. 

Problem Statement 🤔

You are a shinobi of the hidden village of mist. You are assigned a mission to retrieve the scroll of secrets. But the guardian of the scroll is an old turtle. The turtle gave you a problem checking whether you are worthy of the scroll or not. 

problem statement

The problem is to check if the graph can be divided into two cliques. You are provided with an undirected graph. It will have ‘N’ nodes and ‘M’ edges. Your task is to check whether this graph can be divided into two cliques. If it is possible to divide it into two cliques, you’ll answer him, “Yes, it can be divided”. Otherwise, your answer will be, “No, it can’t”. 

Let’s go through an example to better understand the problem.

Sample Example 🧐

Example 1:

Input:

input

Output:

Yes, it can be divided into two cliques.
output

Explanation:

The above graph can be divided into two cliques. {0, 1, 2} and {3, 4, 5}.

 

Example 2:

input

Output:

No, it can’t be divided into two cliques.

 

Explanation: 

The above graph is not isolated enough to break it down into two. Because it is not bipartite. 

Complement Graph Approach 🧑‍💻

Check if the graph can be divided into two cliques for the problem. A complement graph approach is the most suitable approach. Here we find a complement of the given graph and check whether it is bipartite or not. If the complement is a Bipartite graph. Then the graph can be divided into two sets, U and V. 

approach

There should be no edge connecting the same set of vertices. This means in the original graph, these sets U and V are completely connected. Hence original graph could be divided into two Cliques.

Let’s see the algorithm of the given approach.

Algorithm 🧑‍💻✨

  1. We will create a function that returns true if the subgraph is reachable from the source. To do so
    1. We will create a queue where we will store vertex numbers.
    2. Then we will enqueue from source vertex for BFS traversal.
    3. Now check for all vertices in the queue
      1. Find all non-colored adjacent vertices in the graph.
      2. Check whether an edge from u to v exists 
      3. And the destination v is coloured or not.
      4. Now assign an alternate colour to the adjacent vertices v of u
         
  2. We will create a function which returns true if the graph is bipartite. Else, false. 
    1. We will first create a colour array to store the colours assigned to all vertices.
    2. Now check vertices which are not yet coloured.
       
  3. Now we will check whether a function can be divided into two cliques.
    1. Find the complement of the graph.
    2. Here all values are complemented except diagonal ones.
    3. Now return the value true if it is bipartite. Otherwise, return false.

Implementation 🧑‍💻🌝

#include <bits/stdc++.h>
#include <cmath>
#include<algorithm>

using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
const int V = 5;

//--------------------------------Bipartite Utility Function--------------------------------//
bool Bipartitefxn(int G[][V], int src, int coloringarray[])
{
		coloringarray[src] = 1;
		
	// Creating a queue of vertex numbers 
		queue <int> q;
	// and enqueuing source vertex for BFS traversal
		q.push(src);

		while (!q.empty())
		{
			int u = q.front();
			q.pop();

		// Find all non-colored adjacent vertices
				for (int v = 0; v < V; ++v)
				{
					if (G[u][v] && coloringarray[v] == -1)
					{
					// Assigning alternate color
					coloringarray[v] = 1 - coloringarray[u];
					q.push(v);
					}

					else if (G[u][v] && coloringarray[v] == coloringarray[u])
					return false;
				}
		}

	// Now all vertices are colored with alternate color
	return true;
}

// Fuction will check if a Graph is Bipartite or not. Here, G cannot be connected.
bool checkforBipartite(int G[][V])
{
	int coloringarray[V];
		for (int i = 0; i < V; ++i)
		coloringarray[i] = -1;

	// Checking non colored vertices of graph
		for (int i = 0; i < V; i++)
			if (coloringarray[i] == -1)
			if (Bipartitefxn(G, i, coloringarray) == false)
				return false;

	return true;
}

//--------------------------------Function to check cliques-------------------------------------//
// We will returns true if graph can be divided into two Cliques, otherwise returns false.
bool TwoCliquespossible(int G[][V])
{
	// Find complement of the Graph
	// All values of graph are complemented except the diagonal value
		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 checkforBipartite(GC);
}

//--------------------------------Main Function-------------------------------------//
int main()
{
	    FAST;
		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}
					  };


		TwoCliquespossible(G) ? cout << "Yes, it is possible" :
		cout << "No, it is not";
		return 0;
}

 

Output:

output

Time Complexity ⏳

The time complexity of the above-discussed approach is O(V2). Here V is the vertices present in the graph.

Space Complexity 🌌

The space complexity of the above approach is O(1). As we are not using any extra spaces and each operation in the queue takes O(1) space. The space complexity is constant.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions 

What are Cliques?

A Clique is a subgraph of the graph. Here all the vertices in the subgraph are completely connected with each other.

What is a Bipartite Graph?

The graph with no odd-length cycles is known as the Bipartite graph.

What is the difference between a clique and a complete graph?

A complete graph is often called a clique. The size of the largest clique that can be made up of edges and vertices of G is called the clique number of G.

What are the most basic terms used in graph theory?

Some most basic terms used in graph theory are point, line, vertex, edge, degree of vertices, properties of graphs, etc.

Conclusion

This article briefly discussed the problem to check if the graph can be divided into two cliques.

We hope that this blog had help you enhance your knowledge about the problem and if you would like to learn more, check out our articles Check Identical TreesBoundary Traversal of Binary TreeLevel Order Traversal of a Binary TreeConvert BST to the Greatest Sum TreeReplace each node in a binary tree with a sum of its in order predecessor and successor, and Print Nodes between two given Level Numbers of a Binary Tree. You can also refer to our guided path on the basics of java and many more on our Website.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, and many more! If you wish to test your competency in coding, you may check out the mock test series. You can also participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy learning!

Previous article
Check if a Given Graph is Strongly Connected ( Kosaraju's BFS )🥷🏻
Next article
Maximum number of edge-disjoint paths between two vertices
Live masterclass