Conservation precedence

A museum conservation lab has a bench card for every treatment a damaged panel can receive, and a short list of pairs saying which treatment has to be finished before which. The registrar keeps asking the same question in different words.

The problem

Treatments are numbered 0 to count - 1. The lab holds a list of ordering rules; a rule [a, b] means treatment a must be completed before treatment b can begin. The rules never contradict each other — no treatment ends up required before itself, directly or through a chain.

A rule is only the direct requirement. Requirements chain: if consolidation must precede cleaning and cleaning must precede varnishing, then consolidation is required before varnishing even though no card says so.

You are given a batch of questions. Each question [u, v] asks whether treatment u is required before treatment v, directly or through any chain of rules. Answer all of them.

Input. count — the number of treatments. steps — a list of [a, b] pairs, the direct rules. queries — a list of [u, v] pairs, the questions.

Output. A list of booleans, one per question in the same order, True when u is required before v.

Example.

count = 5
steps = [[0, 2], [1, 2], [2, 3], [3, 4]]
queries = [[0, 4], [4, 0], [1, 3], [0, 1]]   ->  [True, False, True, False]

Treatment 0 leads to 2, then 3, then 4, so 0 is required before 4. Nothing runs the other way, so [4, 0] is False. Treatments 0 and 1 both feed into 2 but neither constrains the other, so [0, 1] is False — independent, not ordered.

A second example, with no rules at all:

count = 3
steps = []
queries = [[0, 1], [1, 0], [0, 0]]   ->  [False, False, False]

Note the last one. A treatment is never a requirement for itself, so [0, 0] is False even though the two numbers match.

Constraints.

• 1 <= count <= 100
• 0 <= len(steps) <= count * (count - 1) / 2, no duplicate rules
• the rules contain no cycle
• 1 <= len(queries) <= 10^4

Hints

Approach

Brute force

Run a fresh traversal for each question: start at u, walk the rules forward, and report whether v turns up. One traversal costs O(count + rules), so 10⁴ questions over 100 treatments cost about 10⁴ × 5,000 = 5 × 10⁷ edge visits, and the same traversal is repeated for every question that shares a start.

The insight

There are only count² possible questions, so compute the whole answer table once and read the batch off it.

The table is the transitive closure: reach[a][b] is true when a chain of rules leads from a to b. It has a self-building structure — if a reaches some middle treatment m and m reaches b, then a reaches b. Sweeping m on the outermost loop is what makes this sound: by the time m is considered, every path whose interior uses only earlier middles is already recorded, so each new middle can only extend paths that are complete.

Algorithm

1. Make a count × count table of False, with the diagonal left False.
2. Set reach[a][b] = True for every direct rule [a, b].
3. For each m from 0 to count - 1, for each a, and if reach[a][m], for each b: if reach[m][b], set reach[a][b] = True.
4. Answer each query [u, v] by reading reach[u][v].

Complexity

Time O(count³ + q) — the triple loop is 10⁶ steps at count = 100, then each of the q questions is a single lookup. Space O(count²) for the table.

Solution

"""Conservation precedence — transitive closure over a treatment order graph."""


def solve(count, steps, queries):
    # reach[a][b] is True once a path a -> ... -> b exists. Self-reach stays
    # False: a treatment is never its own prerequisite.
    reach = [[False] * count for _ in range(count)]
    for before, after in steps:
        reach[before][after] = True
    for mid in range(count):
        row_mid = reach[mid]
        for a in range(count):
            if reach[a][mid]:
                row_a = reach[a]
                for b in range(count):
                    if row_mid[b]:
                        row_a[b] = True
    return [reach[u][v] for u, v in queries]

TESTS = [
    ((5, [[0, 2], [1, 2], [2, 3], [3, 4]], [[0, 4], [4, 0], [1, 3], [0, 1]]),
     [True, False, True, False]),
    ((3, [], [[0, 1], [1, 0], [0, 0]]), [False, False, False]),
    ((2, [[0, 1]], [[0, 1], [1, 0]]), [True, False]),
    ((4, [[0, 1], [1, 2], [2, 3]], [[0, 3], [3, 0], [1, 1]]),
     [True, False, False]),
    ((6, [[0, 1], [2, 3], [4, 5]], [[0, 3], [2, 3], [4, 3], [1, 0]]),
     [False, True, False, False]),
]

Pitfalls

• Seeding the diagonal with True. It is tempting to write reach[i][i] = True because "every node reaches itself", but the lab is asking about requirements: [0, 0] must answer False, and the second example catches it.
• Ordering the loops wrongly. Putting the middle treatment on an inner loop computes only the two-step chains, so on the first example [0, 4] comes back False. The middle must be the outermost of the three loops.
• Returning the answers in a different order from the questions. Grouping the batch by starting treatment to save work, then appending as you go, silently permutes the output; keep the result indexed by the query's position.

Variants

• The cold store keyring — the same reachability question asked once, from one fixed start.
• Cycles and topological order — what happens to a rule list that does contradict itself.