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?
Sign in to answer questions and track your progress
Sign In