Strongly connected components: Kosaraju and Tarjan

The strongly connected components of a directed graph are its largest groups of nodes that can all reach one another along the edge directions. Two linear-time methods find them. Kosaraju’s algorithm runs two depth-first searches, the second over the reversed edges in reverse finishing order. Tarjan’s algorithm runs a single depth-first search with a stack and low-links. Shrinking each component to one node leaves a graph without cycles, the condensation.

The problem: districts of one-way streets

A city has n junctions, numbered 0 to n − 1, and m one-way streets; street (a, b) leads from junction a to a different junction b, and a street may be listed twice. A district is a largest group of junctions in which every junction can drive to every other, following streets the way they point. (A) How many districts are there, and which district holds each junction? (B) The city may open new one-way streets: what is the fewest number that lets every junction reach every other? Limits: 1 ≤ n ≤ 100,000 and 0 ≤ m ≤ 200,000.

• Nine junctions with streets 0→1, 1→2, 2→0, 2→3, 3→4, 4→5, 5→3, 5→6, 6→7, 7→6 and 8→4 form four districts, {0, 1, 2}, {3, 4, 5}, {6, 7} and {8}, and need 2 new streets.
• One junction is one district and needs none.
• Two junctions with the street 0→1 are two districts and need 1, the street 1→0.

The brute force, and why it fails at 100,000 junctions

Search from every junction, and put two junctions in one district when each reaches the other. For part B, try every set of k new streets, for k = 1, 2 and so on, until the city is one district:

"""The brute force for districts of one-way streets: a search from every junction, then a pair of junctions shares a
district when each reaches the other. For the fewest new streets, try every set of k new streets for k = 1, 2, ..."""

from itertools import combinations


def reach_from(n, near, s):
    seen, todo = {s}, [s]
    while todo:
        for v in near[todo.pop()]:
            if v not in seen:
                seen.add(v)
                todo.append(v)
    return seen


def districts(n, streets):
    near = [[] for _ in range(n)]
    for a, b in streets:
        near[a].append(b)
    reach = [reach_from(n, near, s) for s in range(n)]  # n searches, n * n answers kept
    label = [-1] * n
    count = 0
    for u in range(n):
        if label[u] == -1:
            for v in range(n):
                if v in reach[u] and u in reach[v]:
                    label[v] = count
            count += 1
    return count, label


def fewest_new_streets(n, streets):
    if districts(n, streets)[0] == 1:
        return 0, 0
    candidates = [(a, b) for a in range(n) for b in range(n) if a != b]
    tried = 0
    for k in range(1, n + 1):
        for extra in combinations(candidates, k):
            tried += 1
            if districts(n, streets + list(extra))[0] == 1:
                return k, tried


NINE = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6), (6, 7), (7, 6), (8, 4)]
for name, n, streets in [("nine junctions", 9, NINE), ("one junction", 1, []), ("two junctions", 2, [(0, 1)])]:
    count, label = districts(n, streets)
    k, tried = fewest_new_streets(n, streets)
    found = f"fewest new streets {k}, found after trying {tried:,} sets" if k else "no new street needed"
    print(f"{name}: {count} district{'s' * (count != 1)} {label}; {found}")

n, m = 100_000, 200_000
print(f"{n:,} junctions: {n:,} searches of up to {n + m:,} steps, {n * (n + m):,} in all, and {n * n:,} reach answers")
print(f"new streets at {n:,} junctions: {n * (n - 1):,} candidates for a single street alone")

nine junctions: 4 districts [0, 0, 0, 1, 1, 1, 2, 2, 3]; fewest new streets 2, found after trying 589 sets
one junction: 1 district [0]; no new street needed
two junctions: 2 districts [0, 1]; fewest new streets 1, found after trying 2 sets
100,000 junctions: 100,000 searches of up to 300,000 steps, 30,000,000,000 in all, and 10,000,000,000 reach answers
new streets at 100,000 junctions: 9,999,900,000 candidates for a single street alone

It finds four districts and 2 new streets after trying 589 sets. At the limits, though, that is 100,000 searches of up to 300,000 steps, 3 × 10¹⁰ in all, and 10¹⁰ reach answers to keep, about 1.25 GB even at one bit each. Part B is worse: a single new street already has 9,999,900,000 candidates.

What to notice

• Reaching each other is an equivalence. If u and v reach each other, and so do v and w, then u and w do too, so the districts split the junctions into groups that never overlap.
• Between districts, streets go one way. Streets leading from district X to Y and also back would make X and Y one district, so the graph of districts has no cycle.
• Part B lives on that graph. It depends on the sources, districts that no street enters, and the sinks, districts that no street leaves.

Three methods follow:

• Kosaraju’s two passes record the order in which a search finishes the junctions, then search the reversed streets, latest finisher first, collecting one district per start.
• Tarjan’s single pass keeps the current search’s junctions on a stack and closes a district when a junction’s low-link equals its own number.
• The condensation has one node per district and an arrow wherever a street joins two districts.

Kosaraju’s two passes, step by step Pro: opens with a Pro, Premium or Ultimate pass