# Untitled

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

void printSolution(const vector<int>& path);

bool isHamCycle(const vector<vector<bool>>& graph, const vector<int>& path) {
int V = graph.size();
if (graph[path[V - 1]][path[0]] != 1)
return false;

for (int i = 0; i < V - 1; i++)
if (graph[path[i]][path[i + 1]] != 1)
return false;

return true;
}

void hamCycleUtil(const vector<vector<bool>>& graph, vector<int>& path, vector<bool>& visited, int pos) {
int V = graph.size();
if (pos == V) {
if (isHamCycle(graph, path))
printSolution(path);
return;
}

for (int v = 0; v < V; v++) {
if (!visited[v]) {
path[pos] = v;
visited[v] = true;
hamCycleUtil(graph, path, visited, pos + 1);
visited[v] = false;
path[pos] = -1;
}
}
}

void hamCycle(const vector<vector<bool>>& graph) {
int V = graph.size();
vector<int> path(V, -1);
vector<bool> visited(V, false);

path[0] = 0;
visited[0] = true;

hamCycleUtil(graph, path, visited, 1);
}

void printSolution(const vector<int>& path) {
for (int v : path)
cout << v << " ";
cout << path[0] << 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);

return 0;
}```