Wings of the one-way house

Every doorway in the house is a turnstile, and the curator wants the rooms grouped so that any two in a group can be walked between, both ways round.

The problem

The house has rooms rooms numbered 0 to rooms - 1. A doorway [room, next] admits a visitor from room to next and never back.

Two rooms belong to the same wing when a visitor can walk from each to the other, following doorways the way they turn. A room nothing leads back from is a wing on its own.

Report how many wings the house has.

Input. rooms — an integer. doorways — a list of [room, next] pairs.

Output. The number of wings.

Example.

rooms = 5, doorways = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]]   ->  3

Rooms 0, 1 and 2 turn in a ring: one wing. Room 3 can be entered from room 1 but nothing leads back, and room 4 is the same, so each is a wing of its own.

A second example, where the plan looks like a loop and is not:

rooms = 3, doorways = [[0, 1], [1, 2], [0, 2]]   ->  3

Without their arrows the three rooms make a triangle. With them, every doorway points the same way down the house and no room can be returned to.

Constraints.

• 1 <= rooms <= 2 × 10^4
• 0 <= len(doorways) <= 10^5
• 0 <= room < rooms, 0 <= next < rooms, room != next
• a doorway may be listed more than once

Hints

Approach

Brute force

Walk forwards from every room to see what it reaches, then pair rooms off when each reaches the other. The walks alone cost 2 × 10⁴ × 1.2 × 10⁵ = 2.4 × 10⁹ steps, before the 4 × 10⁸ pairs are compared.

The insight

A room's wing is what it reaches and what reaches it at once, so walking forwards to fix an order and then backwards in reverse of that order peels off one wing per start.

A room finishes after everything downstream of it that is not in its own wing, so the last room to finish sits in a wing nothing outside leads into. Walking backwards from there reaches that wing and cannot leak into another; cross it off and the next unsettled finish has the same property.

Algorithm

1. Build the doorways forwards and backwards.
2. Walk forwards from every unseen room, appending a room to an order list when its own walk has nothing left to explore.
3. Take that order in reverse. For each room not yet settled, count one wing and walk backwards from it, settling everything reached.
4. Return the count.

Complexity

Time O(rooms + doorways) — two walks, each touching every room once and every doorway once: 2.4 × 10⁵ steps, not 2.4 × 10⁹. Space O(rooms + doorways) — both lists, the marks and the trail.

Solution

"""Wings of the one-way house — two passes: finish order forwards, then walks backwards."""


def finish_order(rooms, onward):
    """Rooms in the order their walk finishes: a room lands after everything it leads to."""
    seen = [False] * rooms
    order = []
    for start in range(rooms):
        if seen[start]:
            continue
        seen[start] = True
        trail = [(start, iter(onward[start]))]
        while trail:
            room, pending = trail[-1]
            nxt = next(pending, None)
            if nxt is None:
                order.append(room)
                trail.pop()
            elif not seen[nxt]:
                seen[nxt] = True
                trail.append((nxt, iter(onward[nxt])))
    return order


def solve(rooms, doorways):
    onward = [[] for _ in range(rooms)]
    backward = [[] for _ in range(rooms)]
    for room, nxt in doorways:
        onward[room].append(nxt)
        backward[nxt].append(room)

    settled = [False] * rooms
    wings = 0
    for room in reversed(finish_order(rooms, onward)):
        # Invariant: the latest unsettled finish belongs to a wing nothing unsettled
        # leads into, so walking backwards from it reaches that wing and no other.
        if settled[room]:
            continue
        wings += 1
        stack = [room]
        settled[room] = True
        while stack:
            here = stack.pop()
            for previous in backward[here]:
                if not settled[previous]:
                    settled[previous] = True
                    stack.append(previous)
    return wings

TESTS = [
    ((5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]]), 3),
    ((3, [[0, 1], [1, 2], [0, 2]]), 3),          # a triangle, but every door points one way round
    ((4, [[0, 1], [1, 2], [2, 3], [3, 0]]), 1),  # the whole house is one loop
    ((3, []), 3),                                # no doorways: three wings of one room
    ((2, [[0, 1], [1, 0]]), 1),
    ((6, [[0, 1], [1, 0], [2, 3], [3, 2], [4, 5]]), 4),
    ((1, []), 1),
]

Pitfalls

• Ignoring the arrows. Treating a doorway as passable both ways makes the second example one wing and answers 1.
• Walking backwards from any room you like. A backwards walk started at room 4 of the first example reaches room 3, then 1, then 2 and 0 — the whole house as one wing, answer 1. Only the reverse finish order starts a walk in a wing nothing outside leads into.
• Recursing either walk. A house of 2 × 10⁴ rooms in one chain recurses that deep, past the interpreter's limit; an explicit trail has no such ceiling.

Variants

• The tunnel to seal — a cycle found in a graph whose edges have no direction to follow.
• Cycles and topological order — the order these walks give when no wing holds more than one room.