Last Updated: 26 Feb, 2021
Two cliques
Moderate
Asked in companies
You are given an undirected graph of ‘N’ nodes and ‘M’ edges. Your task is to print 1 if this graph can be divided into exactly two disjoint cliques. Else, you need to print 0.
Note :
Let G be a subgraph of the given graph. Then, G is said to be a clique if G is a complete graph.
Two cliques are said to be disjoint if they don’t have a common node.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘M’. Here ‘N’ denotes the total number of nodes and ‘M’ denotes the total number of edges in the graph.
The next ‘M’ lines contain two space-separated integers ‘U’ and ‘V’. Here ‘U’ and ‘V’ represent the nodes that share an edge.
Output Format :
For each test case, print 1 if the given graph can be divided into exactly two disjoint cliques, else print 0.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 100
1 <= M <= N * (N - 1) / 2
0 <= U, V <= N - 1
Approaches
The idea here is first to take a complement of the graph. Then the problem reduces to check if the given graph is a bipartite graph or not. Because bipartite is a graph that can be divided into two sets such that no two nodes of the same set have a common edge it means in the original graph every two nodes of the same set are completely connected i.e. the set will be a complete graph.
To check whether a graph is bipartite or not we will color the graph using 2 colors such that adjacent elements will have different colors. If we are not able to do such coloring then it shows that the bipartite graph is not possible.
Algorithm:
- Declare the following things:
- A 2-D array to store the adjacency matrix of the graph, say ‘adj’.
- A color array to keep track of colors of the nodes and initialize all elements of the color array with -1.
- Build an adjacency matrix of complement graph using the given edge list.
- Run a loop from i = 0 to ‘N’. Here, ‘N’ is the total number of nodes in the given graph.
- Check if the subgraph starting at node ‘i’ is a bipartite graph or not, by calling the ‘isBipartite’ function. If the ‘isBipartite’ function returns false then return false.
- Return true as the given graph is a bipartite graph.
Description of isBipartite function :
This function is used to check whether the subgraph starting from vertex ‘u’ is a bipartite graph or not.
This function will take 3 arguments
- A variable ‘u’ denoting the starting node.
- An array ‘color’ to keep track of colors of nodes of the graph.
- A 2 – D array ‘adj’ denotes the adjacency matrix of the graph.
bool isBipartite(u, color, adj) :
- Assign ‘u’ as color = 0.
- Declare an empty queue say, ‘q’, and push ‘u’ to it.
- Run a loop until ‘q’ is not empty:
- Pop front node from ‘q’ say, ‘current’.
- Visit all neighbours of the ‘current’ node:
- Say current neighbor of ‘current’ is v.
- If the color of v equals -1 then assign color equals to (color[current] ^ 1 ) as we need to assign different colors to adjacent nodes. Also push v into the queue.
- Else if ‘color[current]’ equals to ‘color[v]’ then return false as two–coloring is not possible in this subgraph and hence the given graph is not a bipartite graph.
- Return true as we have colored all adjacent nodes in different colors.