GT clieque

 #include <iostream>

#include <vector>

using namespace std;

int n;

vector<vector<bool>> graph;

// checks if the subgraph formed by the given

// vertices is a complete graph or not

bool IsClique(vector<int>& vertices) {

int size = vertices.size();

for(int i = 0; i < size; ++i) {

int u = vertices[i];

for(int j = i + 1; j < size; ++j) {

int v = vertices[j];

if(graph[u][v] == false) {

return false;

}

}

}

return true;

}

vector<int> maximum_clique;

int count = 0;

void FindMaximumClique(int index, vector<int> vertices) {

// we have reached the end of the list

if(index > n) {

if(vertices.size() > 0 && IsClique(vertices)) {

if(vertices.size() > maximum_clique.size()) {

maximum_clique = vertices;

}

count += 1;

//cout<<"Clique #"<<count<<": ";

// for(int num : vertices)

// cout<<num<<" ";

// cout<<endl;

}

return ;

}

// Skip the current vertex

FindMaximumClique(index + 1, vertices);

// Add the current vertex into the list

vertices.push_back(index);

FindMaximumClique(index + 1, vertices);

}

int main() {

cout<<"Enter number of vertices: ";

cin>>n;

cout<<"Enter the graph as an adjacency matrix: "<<endl;

graph = vector<vector<bool>>(n + 1, vector<bool>(n + 1));

for(int i = 1; i <= n; ++i) {

for(int j = 1; j <= n; ++j) {

int value;

cin>>value;

graph[i][j] = value;

}

}

cout<<endl;

FindMaximumClique(1, {});

cout<<"\nMaximum Clique is of size "<<maximum_clique.size()<<endl;

for(int num : maximum_clique) {

cout<<num<<" ";

}

cout<<endl;

}