Round Trip
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:
tois an ancestor ofv: iftowere a descendant ofv, DFS would have found the same edge earlier, from the side ofto;- the cycle is the path of tree edges from
todown tov, closed by the edgev–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";
}