Find cycles path in a directed graph

findCycle.cpp

// https://cses.fi/problemset/task/1678/
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

bool findCycle(vector<vector<ll>> &graph, vector<bool> &visited, vector<bool> &on_stack, vector<ll> &cycle, ll u) {
    visited[u] = true, on_stack[u] = true;
    for (ll i : graph[u]) {
        if (on_stack[i]) {  // encounter a cycle
            cycle.push_back(u);
            on_stack[u] = false, on_stack[i] = false;
            return true;
        }
        if (visited[i]) {
            continue;
        }
        if (findCycle(graph, visited, on_stack, cycle, i)) {  // found cycle and backtracking to find cycle path
            cycle.push_back(u);
            if (on_stack[u]) {
                on_stack[u] = false;
                return true;
            }
            // stop when encounter cycle begin vertex
            return false;
        }
        if (!cycle.empty()) return false;  // if have cycle then stop
    }
    on_stack[u] = false;
    return false;
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> graph(n + 1);
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    vector<bool> visited(n + 1), on_stack(n + 1);
    vector<ll> cycle;
    for (ll i = 1; i <= n; i++) {
        findCycle(graph, visited, on_stack, cycle, i);
        if (!cycle.empty()) break;
    }
    if (cycle.empty())
        cout << "IMPOSSIBLE";
    else {
        reverse(cycle.begin(), cycle.end());
        cout << cycle.size() + 1 << '\n';
        for (ll i : cycle) cout << i << ' ';
        cout << cycle[0];
    }
}