Message Route
A network has \(n\) computers and \(m\) connections. Uolevi’s computer is \(1\) and Maija’s computer is \(n\).
Can Uolevi send a message to Maija? If yes, find a route with the minimum number of computers.
Constraints:
- \(2 \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 connection between computers \(a\) and \(b\). Every connection joins two different computers, and there is at most one connection between two computers.
Output:
- If a route exists: first the number \(k\) of computers on a shortest route, then the \(k\) computers of such a route in order. If there are several, print any of them.
- Otherwise:
IMPOSSIBLE.
Example:
Input:
5 5
1 2
1 3
1 4
2 3
5 4
Output:
3
1 4 5
Solution
The computers are nodes of an undirected graph, and the connections are its edges. A route with the minimum number of computers is a shortest path from node \(1\) to node \(n\), so we run BFS from node \(1\), as in the lesson on BFS.
To print the route, and not only its length, we store for every node to the node parent[to] from which BFS reached it. Then we walk from \(n\) back to \(1\) along the parents and reverse the list. Node \(1\) has parent \(0\), which stops the walk.
If BFS never reaches node \(n\), the answer is IMPOSSIBLE.
The time complexity is \(O(n + m)\).
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> dist(n + 1, -1);
vector<int> parent(n + 1, 0);
queue<int> q;
dist[1] = 0;
q.push(1);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int to : g[v]) {
if (dist[to] != -1) continue; // already visited
dist[to] = dist[v] + 1;
parent[to] = v;
q.push(to);
}
}
if (dist[n] == -1) {
cout << "IMPOSSIBLE\n";
return 0;
}
// walk back from n to 1 along the parents
vector<int> path;
for (int v = n; v != 0; v = parent[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
cout << path.size() << "\n";
for (int v : path) {
cout << v << ' ';
}
cout << "\n";
}