Round Trip

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

Example:

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

Output:

4
1 3 5 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, int par)
{
    color[node] = 1;
    for (int child : arr[node])
    {
        if (child == par)
            continue;
        if (color[child] == 0)
        {
            parent[child] = node;
            if (dfs(child, parent[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, parent[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 = 5, m = 6;
    vector<vector<int>> edges = {{1, 3},
                                 {1, 2},
                                 {5, 3},
                                 {1, 5},
                                 {2, 4},
                                 {4, 5}};
    for (int i = 0; i < m; i++)
    {
        int a = edges[i][0], b = edges[i][1];

        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    findCycle();
    return 0;
}