Skip to content

BFS with Parity States

In one sentence

Breadth-first search visits vertices in order of distance; if the question is about walks of an exact length, search over states (vertex, number of steps is even/odd) instead of plain vertices.

1. What problem does it solve?

Example — AIO 2019 · Evading Capture (AIO 2019 Q5, lesson of 22 August)

There are \(N\) cities and \(E\) undirected roads. You start in city \(X\) and must make exactly \(K\) hops, each to a neighbouring city (you may revisit cities and roads). In how many different cities could you finish?

Limits: \(N, E \le 10^5\), \(K \le 10^9\). It is guaranteed that at least one sequence of \(K\) hops exists.

Input        Output
6 5 4 2
3 1
3 2
1 2
4 2
3 6          3

From city 4 the two-hop walks are \(4 \to 2 \to 1\), \(4 \to 2 \to 3\) and \(4 \to 2 \to 4\).

The naive way. Keep the set of cities reachable after \(1, 2, \dots, K\) hops. Each step costs \(O(N + E)\), and \(K\) can be \(10^9\).

The observation. Once you can stand in a city \(v\) after \(d\) hops, you can also stand there after \(d + 2\), \(d + 4\), … hops: walk to a neighbour and straight back. So only two things matter for \(v\): the fewest even number of hops that reaches it and the fewest odd number.

2. The math

2.1 BFS in one paragraph

BFS starts from the source with distance \(0\) and uses a queue. It pops the front state \(u\) and gives every not-yet-seen neighbour distance \(d(u) + 1\), pushing it to the back. Because the queue always holds states in non-decreasing distance order, the first time a state is reached is along a shortest route. Every state is pushed once and every edge is looked at a constant number of times: \(O(N + E)\).

2.2 The state graph

Make two copies of every city: \((v, 0)\) = "at \(v\) after an even number of hops" and \((v, 1)\) = "after an odd number". A road \(u - v\) connects \((u, 0)\) with \((v, 1)\) and \((u, 1)\) with \((v, 0)\), since every hop flips the parity. BFS from \((X, 0)\) gives

\[ \texttt{dist}[v][p] = \text{fewest hops ending at } v \text{ with parity } p . \]

2.3 The answer

City \(v\) can be the finish exactly when \(\texttt{dist}[v][K \bmod 2] \le K\).

  • Necessary: a walk of exactly \(K\) hops ending at \(v\) has parity \(K \bmod 2\), so the shortest such walk is at most \(K\).
  • Sufficient: take the shortest walk of the right parity, length \(d \le K\). The spare \(K - d\) hops are an even number; burn them by bouncing along one road next to \(v\). Such a road exists: if \(d > 0\) we arrived at \(v\) along one; if \(d = 0\) then \(v = X\), and since some \(K \ge 1\) hop walk exists, \(X\) has a neighbour.

2.4 Trace on sample 1

Neighbours: \(1:\{3,2\}\), \(2:\{3,1,4\}\), \(3:\{1,2,6\}\), \(4:\{2\}\), \(6:\{3\}\), \(5:\{\}\). BFS from \((4, 0)\):

A state \((u, p)\) sends each neighbour \(v\) to \((v, 1 - p)\).

pop distance of popped new states
(4,0) 0 (2,1)
(2,1) 1 (3,0), (1,0)
(3,0) 2 (1,1), (6,1)
(1,0) 2 (3,1)
(1,1) 3 (2,0)
(6,1) 3 —
(3,1) 3 (6,0)
(2,0) 4 (4,1)
(6,0), (4,1) 4, 5 —
city \(v\) 1 2 3 4 5 6
dist[v][0] (even) 2 4 2 0 ∞ 4
dist[v][1] (odd) 3 1 3 5 ∞ 3

\(K = 2\) is even, so count cities with an even distance \(\le 2\): cities \(1\) (2), \(3\) (2) and \(4\) (0). Answer 3.

3. The code from class (22 August)

This is the program we wrote together. dist[u][p] is the BFS distance of state \((u, p)\), and the comments are our thinking at the board. It passes all three official samples.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, e, x, k;
    cin >> n >> e >> x >> k;

    vector<vector<int> > adj(n + 1);

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

    vector<vector<int> > dist(n + 1, vector<int>(2,INT_MAX));
    dist[x][0] = 0;

    queue<pair<int, int> > q;
    q.push({x, 0});

    while (!q.empty()) {
        int u = q.front().first;
        int p = q.front().second;
        q.pop();

        for (auto v: adj[u]) {
            if (dist[v][p ^ 1] == INT_MAX) {
                dist[v][p ^ 1] = dist[u][p] + 1;
                q.push({v, p ^ 1});
            }
        }
    }

    // if dist[i] > k ?
    // no matter how we move, we can't go to vertex i

    // if dist[i] < k

    // if dist[i]%2 == k%2
    // then it's good

    // if dist[i]%2 != k%2

    int p = k % 2;
    int ans = 0;
    for (int u = 1; u <= n; u++) {
        if (dist[u][p] <= k) {
            ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

p ^ 1 flips \(0 \leftrightarrow 1\), which is exactly "one more hop changes the parity". Unreached states keep INT_MAX, which is larger than any \(K \le 10^9\), so they are never counted.

4. The general pattern: state = vertex × extra information

Parity is the simplest "extra information". The same trick answers many other questions: add whatever you need to remember to the state and run BFS on the bigger graph.

Extra information State Number of states
parity of the number of steps \((v, p)\), \(p \in \{0,1\}\) \(2N\)
steps modulo \(m\) \((v, s \bmod m)\) \(mN\)
"have I used my one teleport yet?" \((v, \text{used})\) \(2N\)
which keys I carry (few keys) \((v, \text{mask})\) \(2^k N\) (see bitmasks)

5. Common mistakes

Marking visited per vertex instead of per state

If visited[v] is shared by both parities, reaching \(v\) at an odd distance blocks the even one. Every state needs its own entry.

Simulating \(K\) steps

\(K\) is up to \(10^9\). Any loop over the number of hops is too slow; the parity argument replaces it.

Forgetting the start state

Set dist[x][0] = 0 and push it before the loop. City \(X\) itself counts when \(K\) is even.

Queue of vertices only

Push the pair (v, parity), not just v, otherwise you do not know which copy you popped.

6. Practice

Problem Where Idea
AIO 2019 · Evading Capture AIO 2019 Q5 this page
AIO 2025 · Robot Writing AIO 2025 Q6 the same "distance fits and parity matches" test, on a line
CSES · Labyrinth CSES plain BFS on a grid, recover the path
CSES · Message Route CSES plain BFS shortest path in a graph
Credits & licenses
  • §3 is the program written in class on 22 August, unchanged. Sample data is from the official AIO 2019 statement on ORAC.
  • The BFS summary, state-graph argument, proof of the answer, trace, table and mistakes are ours.