Snatch

#include <iostream>
#include <vector>
#include <random>
#include <unordered_set>

using namespace std;

vector<vector<int>> generateRandomGraph(int numVertices, int numEdges) {
    vector<vector<int>> adj(numVertices);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<int> dis(0, numVertices - 1);

    for (int i = 0; i < numEdges; ++i) {
        int from = dis(gen);
        int to = dis(gen);
        adj[from].push_back(to);
    }

    cout << "Generated graph (adjacency lists):" << endl;
    for (int i = 0; i < numVertices; ++i) {
        cout << i << " -> ";
        for (int v : adj[i]) {
            cout << v << " ";
        }
        cout << endl;
    }

    return adj;
}

vector<vector<int>> inputGraph() {
    int numVertices, numEdges;
    cout << "Enter the number of vertices and edges of the graph: " << endl;
    cin >> numVertices >> numEdges;

    vector<vector<int>> adj(numVertices);

    cout << "Enter the edges in the 'u v' format where u -> v:" << endl;
    for (int i = 0; i < numEdges; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    cout << "Entered graph (adjacency lists):" << endl;
    for (int i = 0; i < numVertices; ++i) {
        cout << i << " -> ";
        for (int v : adj[i]) {
            cout << v << " ";
        }
        cout << endl;
    }

    return adj;
}

void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& path) {
    visited[v] = true;
    path.push_back(v);
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u, adj, visited, path);
        } else {
            cout << "Cycle found: ";
            for (int i = 0; i < path.size(); ++i) {
                if (path[i] == u) {
                    for (int j = i; j < path.size(); ++j) {
                        cout << path[j] << " ";
                    }
                    cout << endl;
                    break;
                }
            }
        }
    }
    path.pop_back();
}

void findCycles(vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<int> path;

    for (int v = 0; v < n; ++v) {
        if (!visited[v]) {
            dfs(v, adj, visited, path);
        }
    }
}

int main() {
    string a;
    cout << "To enter your graph enter - 1, to generate random - 2"
         << ",the default graph is something else." << endl;
    cin >> a;
    if (a == "1") {
        vector<vector<int>> adj1 = inputGraph();
        findCycles(adj1);
    } else if (a == "2") {
        int numVertices, numEdges;
        cout << "Enter the number of vertices: ";
        cin >> numVertices;

        int minEdges = numVertices - 1;
        cout << "Enter the number of edges (at least " << minEdges << "): ";
        cin >> numEdges;

        if (numEdges < minEdges || numEdges > numVertices * (numVertices - 1)) {
            cout << "Invalid number of edges. Exiting program." << endl;
            return 1;
        }

        vector<vector<int>> adj1 = generateRandomGraph(numVertices, numEdges);
        findCycles(adj1);
    } else {
        vector<vector<int>> adj = {{1}, {2}, {3, 4}, {0}, {5}, {4}};
        cout << "Default graph (adjacency lists):" << endl;
        for (int i = 0; i < adj.size(); ++i) {
            cout << i << " -> ";
            for (int v : adj[i]) {
                cout << v << " ";
            }
            cout << endl;
        }

        findCycles(adj);
    }

    return 0;
}