Untitled

unknown
plain_text
2 months ago
1.6 kB
1
Indexable
Never
```#include <iostream>
#include <vector>
using namespace std;

void printSolution(int path[]);

bool hamCycleUtil(const vector<vector<bool>>& graph, int path[], int pos, int V) {
if (pos == V) {
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}

for (int v = 1; v < V; v++) {
if (graph[path[pos - 1]][v] == 1 && path[v] == -1) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1, V))
return true;
path[pos] = -1;
}
}

return false;
}

bool hamCycle(const vector<vector<bool>>& graph, int V) {
int* path = new int[V];
for (int i = 0; i < V; i++)
path[i] = -1;

path[0] = 0;
if (hamCycleUtil(graph, path, 1, V) == false) {
cout << "\nSolution does not exist";
delete[] path;
return false;
}

printSolution(path);
delete[] path;
return true;
}

void printSolution(int path[]) {
cout << "Solution Exists: Following is one Hamiltonian Cycle \n";
for (int i = 0; i < V; i++)
cout << path[i] << " ";

cout << path[0] << " ";
cout << endl;
}

int main() {
int V;
cout << "Enter the number of vertices (V): ";
cin >> V;

vector<vector<bool>> graph(V, vector<bool>(V, false));

cout << "Enter the adjacency matrix for the graph (0 or 1):\n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
cin >> graph[i][j];
}
}

hamCycle(graph, V);

return 0;
}```