⚔️ 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;
}