uniolympiads Ελληνικά

BFS and 0-1 BFS

Shortest distances in an unweighted graph in O(n+m)O(n + m). With weights only 0 and 1, the same with a double-ended queue.

When

"Minimum number of moves", "shortest route in a maze", "is the graph bipartite?". Whenever every step costs the same.

The idea

The queue releases vertices in increasing order of distance: first all those at distance dd, then all at d+1d + 1. That is why the first time we see a vertex, the distance we give it is already final. Each vertex enters the queue once and each edge is examined once (twice in an undirected graph).

To find the route as well as its length, store parent[v] = u at the moment you discover vv and follow the parents back from the end.

0-1 BFS. With weights 0 or 1, an edge of weight 0 does not change the "level". Push the neighbour to the front of the deque if the edge is 0, to the back if it is 1. The deque stays sorted by distance, with no heap. Here, however, a vertex can be improved after it has been discovered, so the test is dist[u] + w < dist[v] and not "not visited yet".

Pitfalls

  • In a grid the vertices are cells. Do not build an adjacency list: keep the four dr, dc and check the bounds.
  • For bipartiteness (Building Teams) run BFS from every vertex that has no colour yet. The graph may be disconnected.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/bfs.cpp
// Breadth-first search on an unweighted graph: shortest distances in edges from src.
// dist[v] = -1 if v is unreachable. O(n + m).
// Plus 0-1 BFS: edge weights 0 or 1, a deque instead of Dijkstra's heap. O(n + m).

vector<int> bfs(const vector<vector<int>>& adj, int src) {
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// adj[u] = list of (v, w) with w in {0, 1}. Unreachable: LLONG_MAX.
vector<ll> zeroOneBfs(const vector<vector<pair<int, int>>>& adj, int src) {
    int n = adj.size();
    vector<ll> dist(n, LLONG_MAX);
    deque<int> dq;
    dist[src] = 0;
    dq.push_back(src);
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (w == 0) {
                    dq.push_front(v);
                } else {
                    dq.push_back(v);
                }
            }
        }
    }
    return dist;
}

Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.