Dependencies, cycles, and a valid order

Two questions with one algorithm: is there a cycle, and if not, what order satisfies everything.

Why it works

Repeatedly take whatever has nothing left blocking it

Count, for each node, how many things must come before it. Start with everything whose count is zero, since those are unblocked. Take one, output it, and reduce the count of everything that depended on it. Anything whose count reaches zero is now unblocked.

The invariant: the queue always holds exactly the nodes with no unsatisfied prerequisites. When the process ends, either everything was output, or the remainder is stuck in a cycle.

That final comparison is the cycle detection. Count what came out; if it is fewer than the number of nodes, the rest form a cycle.

Below, the counts are built and then a single node is taken out, so that the releasing step is visible on its own.

1from collections import defaultdict2 3pairs = [(0, 1), (0, 2), (1, 3), (2, 3)]     # (before, after)4count = 45 6after = defaultdict(list)7blocked_by = [0] * count8for before, later in pairs:9    after[before].append(later)10    blocked_by[later] += 111 12print("blocked_by:", blocked_by)13print("unblocked to start:", [n for n in range(count) if blocked_by[n] == 0])14 15for follower in after[0]:                    # take 0 out and see what it frees16    blocked_by[follower] -= 117 18print("blocked_by after taking 0:", blocked_by)19print("unblocked now:", [n for n in range(1, count) if blocked_by[n] == 0])

Node 3 is still blocked, because only one of the two things it waits on has gone.

Find the bug· 5 min

Find the reversed edge

This is meant to count, for each node, how many things must come before it. On the pairs [(0, 1), (0, 2)] it reports [2, 0, 0] when it should report [0, 1, 1]. Click the line that is wrong.

Click the line you think is wrong

Problem· 25 min

Course Schedule

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 22 min

Course Schedule Ii

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1from collections import defaultdict2 3pairs = [(0, 1), (0, 2), (1, 3), (2, 3)] # (before, after)4count = 45 6after = defaultdict(list)7blocked_by = [0] * count8for before, later in pairs:9 after[before].append(later)10 blocked_by[later] += 111 12print("blocked_by:", blocked_by)13print("unblocked to start:", [n for n in range(count) if blocked_by[n] == 0])14 15for follower in after[0]: # take 0 out and see what it frees16 blocked_by[follower] -= 117 18print("blocked_by after taking 0:", blocked_by)19print("unblocked now:", [n for n in range(1, count) if blocked_by[n] == 0])