Link: CS Academy
(scroll down and go to shortest path section you will find the question)
Code:
from collections import deque
n, m, v = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
x, y = map(int, input().split())
g[x-1].append(y-1)
q = deque()
d = [float('inf') for _ in range(n)]
d[v-1] = 0
vis = [False for _ in range(n)]
vis[v-1] = True
q.append(v-1)
# print(q)
while q:
c = q.pop()
# print(c, q)
for i in g[c]:
if not vis[i]:
q.append(i)
vis[i] = True
d[i] = d[c] + 1
# print(d)
ans = []
for i in range(n):
ans.append(d[i] if d[i] != float('inf') else -1)
print(' '.join(list(map(str, ans))))
Does anyone know why this BFS is wrong?
