Prompt Title: find a cycle in a directed graph

To detect a cycle in a directed graph, you can use the Depth-First Search (DFS) algorithm. You will need to maintain three states for each vertex: unvisited, in the current DFS branch (temporary marked), and visited (permanent marked). If you find a vertex that is temporarily marked while traversing, it means that there is a cycle in the graph. Here is the C++ code to implement this approach:

cppCopy code
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

enum VertexState {
    UNVISITED,
    TEMP_MARKED,
    PERM_MARKED
};

bool dfs(int vertex, vector<vector<int>>& graph, vector<VertexState>& state, stack<int>& cycle) {
    state[vertex] = TEMP_MARKED;
    cycle.push(vertex);

    for (int neighbor : graph[vertex]) {
        if (state[neighbor] == TEMP_MARKED) {
            return true;
        } else if (state[neighbor] == UNVISITED && dfs(neighbor, graph, state, cycle)) {
            return true;
        }
    }

    state[vertex] = PERM_MARKED;
    cycle.pop();
    return false;
}

vector<int> find_cycle(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<VertexState> state(n, UNVISITED);
    stack<int> cycle;

    for (int i = 0; i < n; ++i) {
        if (state[i] == UNVISITED && dfs(i, graph, state, cycle)) {
            vector<int> cycle_vec(cycle.size());
            for (int j = cycle_vec.size() - 1; j >= 0; --j) {
                cycle_vec[j] = cycle.top();
                cycle.pop();
            }
            return cycle_vec;
        }
    }

    return {};
}

int main() {
    // Example graph represented as an adjacency list
    vector<vector<int>> graph = {
        {1, 2},
        {3},
        {0},
        {4},
        {5},
        {3}
    };

    vector<int> cycle = find_cycle(graph);

    if (!cycle.empty()) {
        cout << "Cycle found: ";
        for (int vertex : cycle) {
            cout << vertex << " ";
        }
        cout << endl;
    } else {
        cout << "No cycle found." << endl;
    }

    return 0;
}

This code defines a simple directed graph using an adjacency list, and then it uses the find_cycle() function to detect if there's any cycle in the graph. If a cycle is found, it prints the vertices in the cycle.