Untitled

#include <iostream>
#include <vector>

void printSolution(int path[], int V);

bool hamCycleUtil(const std::vector<std::vector<int>>& 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 std::vector<std::vector<int>>& 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) {
        std::cout << "\nSolution does not exist";
        delete[] path;
        return false;
    }

    std::cout << "Solution Exists: Following are all Hamiltonian Cycles \n";
    printSolution(path, V);

    delete[] path;
    return true;
}

void printSolution(int path[], int V) {
    for (int i = 0; i < V; i++)
        std::cout << path[i] << " ";
    std::cout << path[0] << " ";
    std::cout << std::endl;
}

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

    std::vector<std::vector<int>> graph(V, std::vector<int>(V, 0));

    std::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++) {
            std::cin >> graph[i][j];
        }
    }

    hamCycle(graph, V);

    return 0;
}