Marked Too Late

This BFS marks a vertex visited when it is popped, not when it is pushed.

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

Run it on the triangle 0-1, 0-2, 1-2 from source 0, with each adjacency list in increasing order. What is returned?

A

[0, 3, 2], because the duplicate copy of 2 is popped after 2 is marked and relaxes 1 one more time

B

[0, 1, 2]

C

[0, 1, 1], which is correct: marking on pop only costs duplicate queue entries, and the first pop of a vertex still happens in its true BFS layer

D

The loop never terminates, because 2 is pushed again every time it is reached