DSA sheet / Graph
Round Trip
Do these first: Message Route
The problem in brief
There are n cities (up to 100 000) and m two-way roads (up to 200 000), with at most one road between any two cities. A round trip starts at a city, goes through at least three different cities using roads, and returns to the start without visiting any other city twice. Print the number of cities in the printed route (counting the start twice) and one such route, or IMPOSSIBLE if there is no round trip. Any valid answer is accepted.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1669.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
When does an undirected graph have no cycle at all? Think about what its components look like.
-
Run a traversal and look at every edge. Some edges discover new nodes (tree edges). What does an edge to an already discovered node, other than the one you just came from, tell you?
-
Given such an extra edge between u and v, the two nodes are already connected through the traversal tree. What do the tree path and the extra edge form together?
-
To extract the tree path between u and v, climb parent pointers. How do you know where the two climbs meet?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
A forest (every component a tree) has no cycles, and any extra edge inside a component closes one. So the question is: is there an edge that does not belong to the traversal forest, and if so, what cycle does it make? Traverse with BFS (or DFS) recording parent and depth. The first time you see an edge from u to an already visited v that is not u’s parent, you have a non-tree edge. The tree path from u to v plus that edge is a cycle, and because the graph has no multi-edges the tree path has at least two edges, so the cycle has at least three cities.
To recover the tree path, climb from the deeper endpoint upward until depths match, then climb both together until the two pointers meet at the lowest common ancestor. Concatenate the two climbs. The habit: prove a structural fact first (extra edge means cycle), then use the cheapest extraction that the traversal already supports (parent pointers plus depth), instead of thinking about cycles in general.
Intuition
Explore the roads like spreading ink from a city. If the ink ever reaches a city it has already coloured by a road other than the one it just travelled, two ink paths have met, and the loop formed by walking back along both paths to their common origin is a round trip.
Approach
- Build adjacency lists.
- For every unvisited city, BFS from it with parent[] and depth[]. For each neighbour v of u: if v is unvisited, set parent[v] = u, depth[v] = depth[u] + 1 and push it; else if v != parent[u], you found a non-tree edge (u, v): stop.
- Build the cycle: climb from u and from v to their lowest common ancestor, collect both climbs, then output u … lca … v followed by u again.
- If no such edge is found print IMPOSSIBLE.
Pitfalls: the graph may be disconnected, so start a BFS from every unvisited city; skip the edge back to the parent; use iterative BFS (deep recursion is unsafe at 10^5 nodes); the printed count includes the repeated start city, so it is the number of distinct cities plus one.
Complexity
O(n + m) time and memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> parent(n + 1, 0), depth(n + 1, 0);
vector<char> seen(n + 1, 0);
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
seen[s] = 1;
vector<int> queue = {s};
for (size_t head = 0; head < queue.size(); head++) {
int u = queue[head];
for (int v : adj[u]) {
if (!seen[v]) {
seen[v] = 1;
parent[v] = u;
depth[v] = depth[u] + 1;
queue.push_back(v);
} else if (v != parent[u]) {
// Non-tree edge (u, v): tree path u..lca..v plus this edge is a cycle.
vector<int> left, right;
int a = u, b = v;
while (depth[a] > depth[b]) { left.push_back(a); a = parent[a]; }
while (depth[b] > depth[a]) { right.push_back(b); b = parent[b]; }
while (a != b) {
left.push_back(a); right.push_back(b);
a = parent[a]; b = parent[b];
}
left.push_back(a);
reverse(right.begin(), right.end());
left.insert(left.end(), right.begin(), right.end());
left.push_back(u);
cout << left.size() << "\n";
for (size_t i = 0; i < left.size(); i++) cout << left[i] << (i + 1 < left.size() ? ' ' : '\n');
return 0;
}
}
}
}
cout << "IMPOSSIBLE\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
a = int(data[2 + 2 * i])
b = int(data[3 + 2 * i])
adj[a].append(b)
adj[b].append(a)
parent = [0] * (n + 1)
depth = [0] * (n + 1)
seen = [False] * (n + 1)
for s in range(1, n + 1):
if seen[s]:
continue
seen[s] = True
queue = [s]
head = 0
while head < len(queue):
u = queue[head]
head += 1
for v in adj[u]:
if not seen[v]:
seen[v] = True
parent[v] = u
depth[v] = depth[u] + 1
queue.append(v)
elif v != parent[u]:
# Non-tree edge (u, v): tree path u..lca..v plus this edge is a cycle.
left, right = [], []
a, b = u, v
while depth[a] > depth[b]:
left.append(a)
a = parent[a]
while depth[b] > depth[a]:
right.append(b)
b = parent[b]
while a != b:
left.append(a)
right.append(b)
a = parent[a]
b = parent[b]
left.append(a)
cycle = left + right[::-1] + [u]
print(len(cycle))
print(" ".join(map(str, cycle)))
return
print("IMPOSSIBLE")
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int m = (int) st.nval;
int[] head = new int[n + 1];
Arrays.fill(head, -1);
int[] next = new int[2 * m];
int[] to = new int[2 * m];
int e = 0;
for (int i = 0; i < m; i++) {
st.nextToken();
int a = (int) st.nval;
st.nextToken();
int b = (int) st.nval;
to[e] = b; next[e] = head[a]; head[a] = e++;
to[e] = a; next[e] = head[b]; head[b] = e++;
}
int[] parent = new int[n + 1];
int[] depth = new int[n + 1];
boolean[] seen = new boolean[n + 1];
int[] queue = new int[n];
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
seen[s] = true;
int qh = 0, qt = 0;
queue[qt++] = s;
while (qh < qt) {
int u = queue[qh++];
for (int k = head[u]; k != -1; k = next[k]) {
int v = to[k];
if (!seen[v]) {
seen[v] = true;
parent[v] = u;
depth[v] = depth[u] + 1;
queue[qt++] = v;
} else if (v != parent[u]) {
// Non-tree edge (u, v): tree path u..lca..v plus this edge is a cycle.
ArrayList<Integer> left = new ArrayList<>(), right = new ArrayList<>();
int a = u, b = v;
while (depth[a] > depth[b]) { left.add(a); a = parent[a]; }
while (depth[b] > depth[a]) { right.add(b); b = parent[b]; }
while (a != b) {
left.add(a); right.add(b);
a = parent[a]; b = parent[b];
}
left.add(a);
Collections.reverse(right);
left.addAll(right);
left.add(u);
StringBuilder sb = new StringBuilder();
sb.append(left.size()).append('\n');
for (int i = 0; i < left.size(); i++) sb.append(left.get(i)).append(i + 1 < left.size() ? ' ' : '\n');
System.out.print(sb);
return;
}
}
}
}
System.out.println("IMPOSSIBLE");
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const m = data[1];
const adj = Array.from({ length: n + 1 }, () => []);
for (let i = 0; i < m; i++) {
const a = data[2 + 2 * i];
const b = data[3 + 2 * i];
adj[a].push(b);
adj[b].push(a);
}
const parent = new Int32Array(n + 1);
const depth = new Int32Array(n + 1);
const seen = new Uint8Array(n + 1);
function solve() {
for (let s = 1; s <= n; s++) {
if (seen[s]) continue;
seen[s] = 1;
const queue = [s];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
for (const v of adj[u]) {
if (!seen[v]) {
seen[v] = 1;
parent[v] = u;
depth[v] = depth[u] + 1;
queue.push(v);
} else if (v !== parent[u]) {
// Non-tree edge (u, v): tree path u..lca..v plus this edge is a cycle.
const left = [];
const right = [];
let a = u;
let b = v;
while (depth[a] > depth[b]) { left.push(a); a = parent[a]; }
while (depth[b] > depth[a]) { right.push(b); b = parent[b]; }
while (a !== b) {
left.push(a);
right.push(b);
a = parent[a];
b = parent[b];
}
left.push(a);
const cycle = left.concat(right.reverse(), [u]);
return `${cycle.length}\n${cycle.join(' ')}`;
}
}
}
}
return 'IMPOSSIBLE';
}
console.log(solve());Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).