0-1 BFS and bipartite checks in Python

Questions 1 to 5 of 7

1. 1. What does this program print? ``python from collections import deque dq = deque() dq.append("cost1-a") dq.appendleft("cost0-b") dq.append("cost1-c") dq.appendleft("cost0-d") out = "" while dq: out += dq.popleft() + " " print(out.strip()) ``

   cost1-a cost1-c cost0-b cost0-dcost0-b cost1-a cost1-c cost0-dcost0-d cost0-b cost1-a cost1-ccost0-d cost1-c cost0-b cost1-a
2. 2. What does this program print? ``python from collections import deque n = 6 g = [[] for _ in range(n)] for a, b in [(0, 1), (1, 2), (2, 3), (3, 4)]: g[a].append(b) g[b].append(a) colour = [-1] * n for s in range(n): if colour[s] != -1: continue colour[s] = 0 q = deque([s]) while q: u = q.popleft() for v in g[u]: if colour[v] == -1: colour[v] = 1 - colour[u] q.append(v) print(colour) ``

   [0, 1, 0, 1, 0, 0][0, 1, 0, 1, 0, 1][1, 0, 1, 0, 1, 0][0, 1, 0, 1, 0, -1]
3. 3. In the 0-1 BFS, a neighbour reached by a cost 0 road goes to the front of the deque. Why?

   Free roads are always listed first in the adjacency list, so they are handled first in every case.Items at the front are never stale, so free roads skip the stale check.The deque must be emptied before a cost 0 road can be used.Its distance equals the distance of the item at the front, so putting it at the front keeps the deque in order of distance.
4. 4. Why does two_colour start a new walk from every vertex that is still uncoloured?

   Each walk flips colours, so every new walk must start with colour 1 for the check to work.The queue can hold only one component at a time.A walk from one part of the graph cannot reach another part, so each part needs its own start. Otherwise a conflict in an unvisited part would go unnoticed.Starting only from vertex 0 gives a different number of colours for the groups.
5. 5. True or false, with a reason: the proof that the deque stays in order (every distance is d or d + 1) still holds when one road costs 2.

   True, because a cost 2 road only adds two steps to the back, and the back holds the largest distance, so the order is kept.False, because a cost 2 road can give d + 2, which sits two above the front and breaks the rule that every distance is d or d + 1.