Round Trip II

Byteland has n cities and m flight connections. Your task is to design a round trip that begins in a city, goes through one or more other cities, and finally returns to the starting city. Every intermediate city on the route has to be distinct.

Example:

Input:  n = 4, m = 5, edges = {{1, 3}, {2, 1}, {2, 4}, {3, 2}, {3, 4}}

Output:

4
1 3 2 1 

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[1000001];
vector<int> color, parent;
int cycle_start, cycle_end;
int n;
bool dfs(int node)
{
    color[node] = 1;
    for (int child : arr[node])
    {
        if (color[child] == 0)
        {
            parent[child] = node;
            if (dfs(child))
                return true;
        }
        else if (color[child] == 1)
        {
            cycle_start = child;
            cycle_end = node;
            return true;
        }
    }
    color[node] = 2;
    return false;
}
void findCycle()
{
    color.assign(n + 1, 0);
    parent.assign(n + 1, -1);
    cycle_start = -1;
    for (int i = 1; i <= n; i++)
        if (color[i] == 0 && dfs(i))
            break;
    if (cycle_start == -1)
        cout << "IMPOSSIBLE\n";
    else
    {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);

        cout << cycle.size() << "\n";
        reverse(cycle.begin(), cycle.end());
        for (int v : cycle)
            cout << v << " ";
        cout << "\n";
    }
}
int main()
{
    int m;
    n = 4, m = 5;
    vector<vector<int>> edges = {{1, 3},
                                 {2, 1},
                                 {2, 4},
                                 {3, 2},
                                 {3, 4}};
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];
        arr[a].push_back(b);
    }
    findCycle();
    return 0;
}