Predict the output
What does this print?
from collections import deque
adj = {0: [1, 2, 3], 1: [4], 2: [4], 3: [4], 4: []}
def pushes(mark_on_push: bool) -> int:
seen = {0}
q = deque([0])
count = 1
while q:
u = q.popleft()
if not mark_on_push:
seen.add(u)
for v in adj[u]:
if v not in seen:
if mark_on_push:
seen.add(v)
q.append(v)
count += 1
return count
print(pushes(True), pushes(False))Choose an answer, then open Show answer below to check it.
Show answer
Answer: A 5 7
Right: marking on pop lets node 4 be queued three times.
Marking on push caps queue entries at one per node, which is what keeps BFS at O(V + E).
Why not the others?
- B 5 5. Node 4 has three parents, and with marking on pop each one queues it.
- C 7 5. Marking on push is the version that queues each node once.