DSA/two_clique_problem.cpp at main · Sakshi-source/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

const int V = 5;


bool isBipartiteUtil(int G[][V], int src, int colorArr[])
{
	colorArr[src] = 1;


	queue <int> q;
	q.push(src);


	while (!q.empty())
	{

		int u = q.front();
		q.pop();


		for (int v = 0; v < V; ++v)
		{

			if (G[u][v] && colorArr[v] == -1)
			{

				colorArr[v] = 1 - colorArr[u];
				q.push(v);
			}


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


	return true;
}


bool isBipartite(int G[][V])
{

	int colorArr[V];
	for (int i = 0; i < V; ++i)
		colorArr[i] = -1;


	for (int i = 0; i < V; i++)
		if (colorArr[i] == -1)
			if (isBipartiteUtil(G, i, colorArr) == false)
				return false;

	return true;
}


bool canBeDividedinTwoCliques(int G[][V])
{

	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 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;
}