DSA sheet / Graph
Message Route
Do these first: Counting Rooms
The problem in brief
A network has n computers (up to 100 000) and m two-way connections (up to 200 000). Print the fewest computers a message needs to pass through going from computer 1 to computer n, followed by one such route. If no route exists, print IMPOSSIBLE.
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/1667.
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.
-
The connections are unweighted, so “shortest” means “fewest edges”. Which traversal explores a graph in order of distance from the start?
-
While searching, remember for each computer which computer you came from the first time you reached it. What does that give you at the end?
-
Walk the remembered “came from” links from computer n back to computer 1. In which order do the computers come out, and what must you do before printing?
-
How do you detect that there is no route? Watch the count you must print: it counts computers, not connections.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Same principle as the grid maze, on a general graph: BFS from the source visits nodes in non-decreasing distance, so the first time it reaches a node it has found a shortest path to it. Then a parent array turns the distances into an actual route: parent[v] is the node from which v was first discovered, and following parents from n leads back to 1 along a shortest path.
The number to print counts computers on the route, which is edges plus one. If BFS ends without ever discovering n, there is no route. The habit: BFS plus parent pointers is your default answer to “shortest path, unit weights, and print the path”. Adjacency lists (not a matrix) keep memory and time linear in the number of edges.
Intuition
Send a message out from computer 1 to all its neighbours, then from those to their neighbours, and so on, wave by wave. The first wave to touch computer n is the shortest route; each computer remembers who told it about the message.
Approach
- Build adjacency lists from the m connections (both directions).
- BFS from 1, recording parent[v] when first discovering v.
- If n was not discovered print IMPOSSIBLE.
- Otherwise follow parent from n to 1, reverse the list, print its length and the computers.
Pitfalls: n = 1 is not possible here (the endpoints differ) but handle a generic graph anyway; do not add duplicates to the queue (mark as discovered when pushing); use fast I/O for up to 2 * 10^5 edges.
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);
vector<int> queue;
queue.reserve(n);
parent[1] = -1;
queue.push_back(1);
for (size_t head = 0; head < queue.size() && parent[n] == 0; head++) {
int u = queue[head];
for (int v : adj[u]) {
if (parent[v] == 0) {
parent[v] = u;
queue.push_back(v);
}
}
}
if (parent[n] == 0) {
cout << "IMPOSSIBLE\n";
return 0;
}
vector<int> path;
for (int v = n; v != -1; v = parent[v]) path.push_back(v);
reverse(path.begin(), path.end());
cout << path.size() << "\n";
for (size_t i = 0; i < path.size(); i++) cout << path[i] << (i + 1 < path.size() ? ' ' : '\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)
parent[1] = -1
queue = [1]
head = 0
while head < len(queue) and parent[n] == 0:
u = queue[head]
head += 1
for v in adj[u]:
if parent[v] == 0:
parent[v] = u
queue.append(v)
if parent[n] == 0:
print("IMPOSSIBLE")
return
path = []
v = n
while v != -1:
path.append(v)
v = parent[v]
path.reverse()
print(len(path))
print(" ".join(map(str, path)))
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;
// Edge lists as linked arrays: head[u] -> next[e] -> ..., to[e] is the neighbour.
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[] queue = new int[n];
int qh = 0, qt = 0;
parent[1] = -1;
queue[qt++] = 1;
while (qh < qt && parent[n] == 0) {
int u = queue[qh++];
for (int k = head[u]; k != -1; k = next[k]) {
int v = to[k];
if (parent[v] == 0) {
parent[v] = u;
queue[qt++] = v;
}
}
}
if (parent[n] == 0) {
System.out.println("IMPOSSIBLE");
return;
}
ArrayList<Integer> path = new ArrayList<>();
for (int v = n; v != -1; v = parent[v]) path.add(v);
Collections.reverse(path);
StringBuilder sb = new StringBuilder();
sb.append(path.size()).append('\n');
for (int i = 0; i < path.size(); i++) sb.append(path.get(i)).append(i + 1 < path.size() ? ' ' : '\n');
System.out.print(sb);
}
}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);
parent[1] = -1;
const queue = [1];
for (let head = 0; head < queue.length && parent[n] === 0; head++) {
const u = queue[head];
for (const v of adj[u]) {
if (parent[v] === 0) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[n] === 0) {
console.log('IMPOSSIBLE');
} else {
const path = [];
for (let v = n; v !== -1; v = parent[v]) path.push(v);
path.reverse();
console.log(`${path.length}\n${path.join(' ')}`);
}Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).