⚔️ E. Quarrel — Synchronized BFS with Two Agents
Hello Codeforces community!
Today, we’ll dive into a unique and elegant graph problem — one that combines classic BFS with a twist: two agents moving simultaneously, and we must avoid collisions not only in space, but also in time.
This is problem E. Quarrel, and it’s not just about finding shortest paths — it’s about simulating two people who hate each other. https://codeforces.me/problemset/problem/29/E
Problem Summary
You're given a graph with n nodes and m edges: - Bob starts at node 1 and wants to go to node n. - Alex starts at node n and wants to go to node 1. - They must move at the same speed and must not be at the same node at the same time. - They can cross each other mid-edge (pass in opposite directions), but not arrive at or leave from the same node simultaneously.
You must: - Find shortest-length paths (with equal length k) for both Alex and Bob. - Ensure they don’t collide in any node at the same time.
Intuition
At first glance, this feels like two BFS traversals. But the constraint that they must not be at the same place at the same time makes this problem richer:
- We want to compute a path for Bob and a path for Alex — same length, start at opposite ends, no overlap at same timestep.
- Since they move simultaneously, we need to simulate time steps and track positions at each time.
- So this becomes a synchronized simulation problem.
Step-by-Step Strategy
Step 1: Precompute Shortest Paths with BFS
Run BFS from node 1 → dist_bob[]
Run BFS from node n → dist_alex[]
These arrays tell us: - dist_bob[v] = min steps from 1 to v - dist_alex[v] = min steps from n to v
Step 2: Find the Shortest Valid Length k
We want the smallest k such that: - There’s at least one path of length k from 1 → n for Bob. - And a reverse path of same length k from n → 1 for Alex. - And at every time t (0 to k), bob_path[t] != alex_path[t]
We can reconstruct all shortest paths using parent arrays, or greedily choose any using BFS traversal order.
Step 3: Reconstruct Both Paths
Use BFS + parent tracking to reconstruct: - A path of length k for Bob from 1 → n - A path of length k for Alex from n → 1
Store these as: cpp vector<int> bob_path(t + 1); vector<int> alex_path(t + 1);
Step 4: Simulate Movement and Check for Conflicts
For i = 0 to k:
If bob_path[i] == alex_path[i]→ conflict
If i > 0 and bob_path[i-1] == alex_path[i] && alex_path[i-1] == bob_path[i] → conflict (crossing same edge in same step)
If no conflict → valid answer.
C++ code
#include <bits/stdc++.h> // Includes most standard libraries
// Using the standard namespace to avoid std:: prefix
using namespace std;
// Max N for convenience, typically N+1 for 1-based indexing
const int MAXN = 501;
// dist[bob_pos][alex_pos] = min_time
// Initialized to -1 (unvisited) by default for global arrays, but explicit initialization is safer.
int dist[MAXN][MAXN];
// parent[bob_pos][alex_pos] = {prev_bob_pos, prev_alex_pos}
pair<int, int> parent[MAXN][MAXN];
// Adjacency list for the graph
vector<int> adj[MAXN];
int main() {
// Optimize C++ standard streams for competitive programming
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
// Read roads and build the adjacency list
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Initialize dist array with -1 (unvisited)
// Using memset for efficiency on large arrays
memset(dist, -1, sizeof(dist));
// BFS queue stores pairs of (Bob's position, Alex's position)
queue<pair<int, int>> q;
// Starting state: Bob at 1, Alex at n, time 0
dist[1][n] = 0;
q.push({1, n});
int final_k = -1; // Stores the minimum time (length of routes)
// BFS loop
while (!q.empty()) {
pair<int, int> current_state = q.front();
q.pop();
int bob_curr = current_state.first;
int alex_curr = current_state.second;
int current_time = dist[bob_curr][alex_curr];
// If we reached the destination (Bob at n, Alex at 1)
if (bob_curr == n && alex_curr == 1) {
final_k = current_time; // This is the shortest time
break; // Found the shortest path, no need to explore further
}
// Iterate through all possible next moves for Bob
for (int bob_next : adj[bob_curr]) {
// Iterate through all possible next moves for Alex
for (int alex_next : adj[alex_curr]) {
// Collision check: they must not land on the same crossroads at the same time
if (bob_next == alex_next) {
continue; // Collision, skip this pair of moves
}
// If this new combined state (bob_next, alex_next) hasn't been visited yet
if (dist[bob_next][alex_next] == -1) {
dist[bob_next][alex_next] = current_time + 1; // Update distance
parent[bob_next][alex_next] = {bob_curr, alex_curr}; // Store parent for path reconstruction
q.push({bob_next, alex_next}); // Enqueue the new state
}
}
}
}
// Output results
if (final_k == -1) {
cout << -1 << endl; // No valid routes found
} else {
cout << final_k << endl; // Print the minimum length of routes
vector<int> bob_path;
vector<int> alex_path;
int curr_bob_pos = n; // Start reconstruction from Bob's destination
int curr_alex_pos = 1; // Start reconstruction from Alex's destination
// Backtrack using the parent array until we reach the starting state (1, n)
while (curr_bob_pos != 1 || curr_alex_pos != n) {
bob_path.push_back(curr_bob_pos);
alex_path.push_back(curr_alex_pos);
pair<int, int> prev_pos = parent[curr_bob_pos][curr_alex_pos];
curr_bob_pos = prev_pos.first;
curr_alex_pos = prev_pos.second;
}
// Add the initial positions to the paths
bob_path.push_back(1);
alex_path.push_back(n);
// Paths were built in reverse order, so print them by iterating backwards
for (int i = bob_path.size() - 1; i >= 0; --i) {
cout << bob_path[i] << (i == 0 ? "" : " ");
}
cout << endl;
for (int i = alex_path.size() - 1; i >= 0; --i) {
cout << alex_path[i] << (i == 0 ? "" : " ");
}
cout << endl;
}
return 0;
}
