Round Trip

Round Trip
CSES medium

A country has \(n\) cities and \(m\) two-way roads. Design a round trip: it starts in a city, goes through two or more other cities, and returns to the starting city. The cities in the middle of the trip must all be different.

Constraints:

  • \(1 \le n \le 10^5\)
  • \(1 \le m \le 2 \cdot 10^5\)
  • \(1 \le a, b \le n\)

Input:

  • First line: two integers \(n\) and \(m\).
  • Next \(m\) lines: two integers \(a\) and \(b\) — a road between cities \(a\) and \(b\). Every road joins two different cities, and there is at most one road between two cities.

Output:

  • If a round trip exists: first the number \(k\) of cities on the trip, then the \(k\) cities in order (the first and the last city are the same). If there are several, print any of them.
  • Otherwise: IMPOSSIBLE.

Example:

Input:

5 6
1 3
1 2
5 3
1 5
2 4
4 5

Output:

4
3 5 1 3
Solution

A round trip is a cycle in the graph. Because there are no repeated roads, every cycle has at least \(3\) cities, as the problem requires.

We run DFS and remember the parent of every node. When DFS at node v sees a neighbor to that is already visited and is not the parent of v, we have found a cycle:

  • to is an ancestor of v: if to were a descendant of v, DFS would have found the same edge earlier, from the side of to;
  • the cycle is the path of tree edges from to down to v, closed by the edge v–to.

We collect the cycle by walking from v up along the parents until we reach to, and we add to at both ends. The order is reversed compared with DFS, but a round trip can be printed in either direction.

If DFS from every unvisited node finds no such edge, the graph is a forest and the answer is IMPOSSIBLE.

The time complexity is \(O(n + m)\).

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> g;
vector<int> parent;
vector<bool> visited;
int cycleStart = 0, cycleEnd = 0;

bool dfs(int v, int p) {
    visited[v] = true;
    parent[v] = p;

    for (int to : g[v]) {
        if (to == p) continue;  // the edge we came from
        if (visited[to]) {
            // an edge to an already visited node closes a cycle
            cycleStart = to;
            cycleEnd = v;
            return true;
        }
        if (dfs(to, v)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    g.resize(n + 1);
    parent.resize(n + 1);
    visited.resize(n + 1, false);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int v = 1; v <= n; v++) {
        if (!visited[v] && dfs(v, 0)) {
            // cycleStart is an ancestor of cycleEnd: collect the tree path between them
            vector<int> route;
            route.push_back(cycleStart);
            for (int u = cycleEnd; u != cycleStart; u = parent[u]) {
                route.push_back(u);
            }
            route.push_back(cycleStart);

            cout << route.size() << "\n";
            for (int u : route) {
                cout << u << ' ';
            }
            cout << "\n";
            return 0;
        }
    }

    cout << "IMPOSSIBLE\n";
}