Unit 20: Round Trips

One-way streets change everything

In an undirected graph, "connected" is simple. With one-way streets you can be able to get from A to B and not back.

Two nodes are strongly connected when each can reach the other. A strongly connected component is a group where that holds for every pair.

Two searches find the component of a node

Everything reachable from node 0, and everything that can reach it — which is the same search on the graph with every arrow turned round.

Whatever is in both lists is in node 0's component.

Python

n = 8
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6), (6, 7), (7, 6)]

adj = [[] for i in range(n)]
rev = [[] for i in range(n)]
for a, b in edges:
    adj[a].append(b)
    rev[b].append(a)

def reach(graph, start):
    seen = [False] * n
    stack = [start]
    while stack:
        node = stack.pop()
        if seen[node]:
            continue
        seen[node] = True
        for nxt in graph[node]:
            if not seen[nxt]:
                stack.append(nxt)
    return set(i for i in range(n) if seen[i])

forward = reach(adj, 0)
backward = reach(rev, 0)
print(sorted(forward))
print(sorted(backward))
print(sorted(forward & backward))

It prints

[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2]
[0, 1, 2]

The whole graph is strongly connected when one node reaches everything both ways

If node 0 can reach everybody and everybody can reach node 0, then any two nodes can get to each other by going via 0.

So checking a whole graph is two searches, not n of them. Three towns in a ring pass; the eight-town map above does not, because nothing can get back once it has left the first three.

Python

n = 3
edges = [(0, 1), (1, 2), (2, 0)]

adj = [[] for i in range(n)]
rev = [[] for i in range(n)]
for a, b in edges:
    adj[a].append(b)
    rev[b].append(a)

def count_reached(graph, start):
    seen = [False] * n
    stack = [start]
    total = 0
    while stack:
        node = stack.pop()
        if seen[node]:
            continue
        seen[node] = True
        total += 1
        for nxt in graph[node]:
            if not seen[nxt]:
                stack.append(nxt)
    return total

print(count_reached(adj, 0), count_reached(rev, 0))
print(count_reached(adj, 0) == n and count_reached(rev, 0) == n)

It prints

3 3
True

Finding every component at once

Two passes. First, a depth-first search of the whole graph, writing down each node when it finishes — the order unit 11 noticed was a topological one.

Then search the reversed graph, taking nodes in reverse finishing order. Each search grabs exactly one component.

The whole algorithm

Eight towns, three components: {0, 1, 2}, {3, 4, 5} and {6, 7}. The comp list gives each node its component number, in the order the second pass found them.

Python

import sys
sys.setrecursionlimit(10000)

n = 8
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6), (6, 7), (7, 6)]
adj = [[] for i in range(n)]
rev = [[] for i in range(n)]
for a, b in edges:
    adj[a].append(b)
    rev[b].append(a)

order = []
seen = [False] * n

def visit(node):
    seen[node] = True
    for nxt in adj[node]:
        if not seen[nxt]:
            visit(nxt)
    order.append(node)

for i in range(n):
    if not seen[i]:
        visit(i)

print(order)

comp = [-1] * n
label = 0
for node in reversed(order):
    if comp[node] != -1:
        continue
    stack = [node]
    while stack:
        x = stack.pop()
        if comp[x] != -1:
            continue
        comp[x] = label
        for nxt in rev[x]:
            if comp[nxt] == -1:
                stack.append(nxt)
    label += 1

print(comp)
print(label)

It prints

[7, 6, 5, 4, 3, 2, 1, 0]
[0, 0, 0, 1, 1, 1, 2, 2]
3

Why the finishing order is the right order

The node that finishes last belongs to a component nothing else points into. Starting the reversed search there, it can only reach its own component — every arrow leading out of it now leads in the wrong direction.

Strip that component off and repeat. Each search is fenced in by the ones already taken.

Tarjan does it in one pass

A single search that tracks how far back each node can reach is enough — that is Tarjan's algorithm, and it is what a fast contestant types.

It is also unit 22's low-link idea in advance. Kosaraju is here because both of its halves are searches you have already written.

Every component becomes one node

Draw each component as a single blob and keep the arrows between blobs. The result — the condensation — can have no cycles, because a cycle between two blobs would have made them one blob.

So it is a DAG, and unit 10's whole toolbox applies to any directed graph at all.

Python

comp = [0, 0, 0, 1, 1, 1, 2, 2]
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6), (6, 7), (7, 6)]

between = set()
for a, b in edges:
    if comp[a] != comp[b]:
        between.add((comp[a], comp[b]))

print(sorted(between))

It prints

[(0, 1), (1, 2)]

What that buys you

Longest chain of towns you can drive through? Count arrows in the condensation, not the graph. Number of towns reachable from here? Add up the sizes of the blobs a blob can reach.

Inside a component everything reaches everything, so the only interesting structure is between them.

Python

comp = [0, 0, 0, 1, 1, 1, 2, 2]
size = [0, 0, 0]
for c in comp:
    size[c] += 1

between = [(0, 1), (1, 2)]
adj = [[] for i in range(3)]
for a, b in between:
    adj[a].append(b)

reach = [0] * 3
for start in reversed(range(3)):
    total = size[start]
    for nxt in adj[start]:
        total += reach[nxt]
    reach[start] = total

print(size)
print(reach)

It prints

[3, 3, 2]
[8, 5, 2]

The component numbers come out in a useful order

Kosaraju numbers the components in a topological order of the condensation — component 0 before anything it points at.

So you can loop over them backwards and have every answer you need already computed, exactly as in unit 10, with no second sort.

How few new roads make everything reachable?

The eight towns fall into three components in a chain. Add one road from the last blob back to the first and every town can reach every other.

The general answer is short, and surprising: count the blobs with no arrows in and the blobs with no arrows out, and take the larger.

Sources and sinks

A blob with nothing pointing at it can never be reached — it needs a new road in. A blob with nothing pointing out can never leave — it needs one out.

Each new road can fix at most one of each, so you need at least the larger count, and pairing them up achieves it.

Python

labels = 3
between = [(0, 1), (1, 2)]

indeg = [0] * labels
outdeg = [0] * labels
for a, b in between:
    outdeg[a] += 1
    indeg[b] += 1

sources = sum(1 for c in range(labels) if indeg[c] == 0)
sinks = sum(1 for c in range(labels) if outdeg[c] == 0)
print(indeg, outdeg)
print(sources, sinks, max(sources, sinks))

It prints

[0, 1, 1] [1, 1, 0]
1 1 1

And the special case that catches everybody

If the whole graph is already one component, the answer is 0 — but the formula says 1, because that single blob has no arrows in and none out.

So check for one component first. A test set will always contain that case.

Python

def answer(labels, indeg, outdeg):
    if labels == 1:
        return 0
    sources = sum(1 for c in range(labels) if indeg[c] == 0)
    sinks = sum(1 for c in range(labels) if outdeg[c] == 0)
    return max(sources, sinks)

print(answer(1, [0], [0]))
print(answer(3, [0, 1, 1], [1, 1, 0]))
print(answer(3, [0, 1, 1], [2, 0, 0]))

It prints

0
1
2

Why one road can only ever fix one of each

A new road leaves one blob and arrives at another. It gives an arrow out to at most one sink, and an arrow in to at most one source.

So with s sources and t sinks you cannot do better than the larger of the two — and joining each sink to the next source round a ring achieves exactly that.