Round Trip II

    1#include <bits/stdc++.h>
    2using namespace std;
    3 
    4void dfs(int u, vector<vector<int>> &adj, vector<int> &parent, vector<int> & colour, vector<int>& cycle, bool &found){
    5    if(found) return;
    6    colour[u] = 1;
    7    for(int nxt : adj[u]){
    8        if(found) return;
    9        if(colour[nxt] == 0){
    10            parent[nxt] = u;
    11            dfs(nxt, adj, parent, colour, cycle, found);
    12        } else if(colour[nxt] == 1){
    13            // find parent and build cycle
    14            int cur = u;
    15            cycle.push_back(nxt);
    16            while(cur != nxt){
    17                cycle.push_back(cur);
    18                cur = parent[cur];
    19            }
    20            reverse(cycle.begin(), cycle.end());
    21            found = true; return;
    22        }
    23    }
    24    colour[u] = 2;
    25}
    26vector<int> find_cycle(vector<vector<int>> &adj){
    27    vector<int> colour(adj.size()), parent(adj.size()); // if colour[i] == 0, it is not visited, colour[1] = visiting, colour[2] = visited
    28    vector<int>cycle;
    29    bool found = 0;
    30    for(int i = 1; i < adj.size() && !found; i++){
    31        if(colour[i] == 0) dfs(i, adj, parent, colour, cycle, found);
    32    }
    33    return cycle;
    34}
    35int main(){
    36    ios::sync_with_stdio(0); cin.tie(0);
    37    int n, m; cin >> n >> m;
    38    vector<vector<int>> adj(n + 1);
    39    vector<int> indegree(n + 1);
    40    for(int i = 0; i < m; i++){
    41        int a, b; cin >> a >> b;
    42        adj[a].push_back(b);
    43        indegree[b]++;
    44    }
    45    queue<int> q;
    46    for(int i = 1; i < indegree.size(); i++){
    47        if(indegree[i] == 0) q.push(i);
    48    } 
    49    int visited = 0;
    50    while(!q.empty()){
    51        int cur = q.front(); q.pop(); visited++;
    52        for(int nxt : adj[cur]){ 
    53            if(!(--indegree[nxt])) q.push(nxt);
    54        }
    55    }
    56    if(visited == n){
    57        cout << "IMPOSSIBLE" << '\n';
    58    } else {
    59        vector<int> cycle = find_cycle(adj);
    60        cout << cycle.size() + 1 << '\n';
    61        for(int i = 0; i < cycle.size(); i++){
    62            cout << cycle[i] << " ";
    63        }
    64        cout << cycle[0] << "\n";
    65    }
    66    return 0;
    67}