Untitled

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