# Untitled

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

using namespace std;

namespace HamiltonianCycle {

void print(int path[], int numVertices) {
cout << "Hamiltonian Cycle:";
for (int i = 0; i < numVertices; i++) {
cout << path[i] << " ";
}
cout << path[0] << endl;
}

void printAllHamiltonianCycles(const vector<vector<int>>& graph, int path[], int pos, int numVertices) {
if (pos == numVertices) {
print(path, numVertices);
return;
}

for (int v = 1; v < numVertices; v++) {
if (graph[path[pos - 1]][v] == 1 && path[v] == -1) {
path[pos] = v;
printAllHamiltonianCycles(graph, path, pos + 1, numVertices);
path[pos] = -1;
}
}
}

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

path[0] = 0;
printAllHamiltonianCycles(graph, path, 1, numVertices);

delete[] path;
return true;
}

}  // namespace HamiltonianCycle

int main() {
int numVertices;
cout << "number of vertices: ";
cin >> numVertices;

vector<vector<int>> graph(numVertices, vector<int>(numVertices, 0));

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

HamiltonianCycle::hamCycle(graph, numVertices);

return 0;
}```