Skip to content

Two-Agent BFS

Two-agent BFS: product state space (pos1, pos2) for simultaneous movement

Two robots stand at opposite ends of a graph. They step simultaneously. Every move, both robots must land on nodes of different colors. One wrong pair and the move is illegal. How do you find the shortest sequence of simultaneous steps to swap their positions?

You can't track them separately. Their fates are coupled.

The Problem: ABC289-E Swap Places

\(N\) nodes, \(M\) edges. Each node is colored red or blue. Takahashi starts at node 1, Aoki at node \(N\). Each turn, both move simultaneously to adjacent nodes. After each move, Takahashi and Aoki must be on nodes of different colors. Find the minimum number of moves for Takahashi to reach \(N\) and Aoki to reach 1, or report \(-1\).

Key insight. Because the constraint involves both positions at once, a single-agent BFS cannot capture it. The state must encode where both agents are.

The Product Graph

Define the state as a pair \((a, b)\) where \(a\) = Takahashi's position and \(b\) = Aoki's position.

  • Start state: \((1, N)\).
  • Goal state: \((N, 1)\).
  • Transition: from \((a, b)\), move to \((a', b')\) where \(a'\) is a neighbor of \(a\), \(b'\) is a neighbor of \(b\), and \(\text{color}[a'] \neq \text{color}[b']\).

This is BFS on a graph of \(N^2\) nodes. Each node is a pair of positions. Each edge in the product graph corresponds to one simultaneous step in the original graph.

Original graph:          Product graph states:
1 -- 2 -- 3              (1,3)  (1,2)  (1,1)
                          (2,3)  (2,2)  (2,1)
Colors: R  B  R           (3,3)  (3,2)  (3,1)

Transitions in Detail

From state \((a, b)\), enumerate all pairs \((a', b')\):

for (int na : adj[a]) {
    for (int nb : adj[b]) {
        if (color[na] == color[nb]) continue;  // same color -> illegal
        if (dist[na][nb] != -1) continue;       // already visited
        dist[na][nb] = dist[a][b] + 1;
        q.push({na, nb});
    }
}

The color constraint prunes many transitions. Without it, every pair of neighbors would be valid and the product graph would be dense.

Gotcha. The product graph has \(N^2\) nodes but up to \(O(M^2)\) edges in the worst case. For \(N = 2000\) and \(M = 4000\), that is \(4 \times 10^6\) nodes and potentially \(16 \times 10^6\) edges. This fits in memory and time for BFS, but just barely.

Trace: Small Example

Graph with 4 nodes. Edges: 1-2, 2-3, 3-4, 1-3.

Colors: node 1 = R, node 2 = B, node 3 = R, node 4 = B.

Start: \((1, 4)\). Goal: \((4, 1)\).

Initial check: color[1] = R, color[4] = B. Different. Valid start.

Step Pop Neighbors checked Valid pushes Queue after
0 (1, 4) (2,3): B,R ✓ (2,3) dist=1 [(2,3)]
1 (2, 3) (1,2): R,B ✓; (1,4): R,B ✓; (3,2): R,B ✓; (3,4): R,B ✓ (1,2)=2, (1,4) skip, (3,2)=2, (3,4)=2 [(1,2),(3,2),(3,4)]
2 (1, 2) (2,1): B,R ✓; (2,3): B,R skip; (3,1): R,R ✗; (3,3): R,R ✗ (2,1)=3 [(3,2),(3,4),(2,1)]
3 (3, 2) (2,1): B,R ✓ skip; (2,3): B,R skip; (4,1): B,R ✓; (4,3): B,R ✓ (4,1)=3, (4,3)=3 [(3,4),(2,1),(4,1),(4,3)]

Found \((4, 1)\) at distance 3.

Path: \((1,4) \to (2,3) \to (3,2) \to (4,1)\). Takahashi goes 1-2-3-4. Aoki goes 4-3-2-1. At every step the colors differ.

Full Solution Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        vector<int> color(N + 1);
        for (int i = 1; i <= N; i++) cin >> color[i];

        vector<vector<int>> adj(N + 1);
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // BFS on product graph
        vector<vector<int>> dist(N + 1, vector<int>(N + 1, -1));
        queue<pair<int,int>> q;

        if (color[1] != color[N]) {
            dist[1][N] = 0;
            q.push({1, N});
        }

        while (!q.empty()) {
            auto [a, b] = q.front(); q.pop();
            for (int na : adj[a]) {
                for (int nb : adj[b]) {
                    if (color[na] == color[nb]) continue;
                    if (dist[na][nb] != -1) continue;
                    dist[na][nb] = dist[a][b] + 1;
                    q.push({na, nb});
                }
            }
        }

        cout << dist[N][1] << "\n";
    }
    return 0;
}

When Product Graphs Explode

The state space is \(N^2\). That's fine when \(N \leq 2000\). But for \(N = 10^5\), you'd need \(10^{10}\) states. Product graph BFS is off the table.

For large \(N\), you need to decouple the agents. That's only possible when the constraint between them is simple enough to factor. Chapters 3 and 5 showed problems where one Dijkstra suffices. This chapter is for the cases where it doesn't.

Key insight. Product graph BFS is the brute-force of multi-agent search. It always works when \(N\) is small. The art is recognizing when you can avoid it.

Decoupled Variant: ABC209-D Collision

\(N\) nodes, \(N - 1\) edges forming a tree. For each query \((A, B)\): two people start at nodes \(A\) and \(B\) and walk toward each other along the unique path. Each second, both move one edge closer. Do they collide at a vertex ("Town") or on an edge ("Road")?

This does not need a product graph. The two agents move on a fixed path.

Key observation: the distance between \(A\) and \(B\) on the tree determines everything.

  • If \(\text{dist}(A, B)\) is even, they meet at the midpoint vertex. Answer: Town.
  • If \(\text{dist}(A, B)\) is odd, they cross on an edge. Answer: Road.

Root the tree and compute depths via BFS. The parity of \(\text{dist}(A, B) = \text{depth}[A] + \text{depth}[B] - 2 \cdot \text{depth}[\text{LCA}(A, B)]\) is the same as the parity of \(\text{depth}[A] + \text{depth}[B]\), since \(2 \cdot \text{depth}[\text{LCA}]\) is always even.

// After computing depths via BFS from root:
for (int q = 0; q < Q; q++) {
    int a, b;
    cin >> a >> b;
    if ((depth[a] + depth[b]) % 2 == 0)
        cout << "Town\n";
    else
        cout << "Road\n";
}

Key insight. When agents are forced onto a single path (as on a tree), you don't need a product graph. The parity of the distance tells you everything about where they meet.

When to Use Product Graph BFS

Ask these questions:

  1. Are two (or more) agents coupled? Their joint behavior depends on both positions.
  2. Is \(N\) small? \(N \leq 2000\) means \(N^2 \leq 4 \times 10^6\). Feasible.
  3. Can the constraint be decoupled? If not, product graph is your only option.

If the answer is yes-yes-no, build the product graph and run BFS.

Exercises

  1. Symmetric pruning. In Swap Places, if Takahashi and Aoki have the same movement rules, is the product graph symmetric? Can you reduce the state space by a factor of 2?

  2. Three agents. If three agents move simultaneously on a graph of \(N = 100\) nodes, how many product states exist? Is BFS still feasible?

  3. No color constraint. If we remove the color constraint from Swap Places, what is the minimum number of swapping steps for any connected graph?

Problems

Problem Link Difficulty
ABC289-E — Swap Places atcoder.jp/contests/abc289/tasks/abc289_e Medium
ABC209-D — Collision atcoder.jp/contests/abc209/tasks/abc209_d Medium
LC 1306 — Jump Game III leetcode.com/problems/jump-game-iii Medium