One call line too many

A county flood-warning scheme rings its stations in a chain: control rings two stations, those ring others, and every station is rung by exactly one. One line in the list does not belong.

The problem

The stations are numbered 1 to n. A call line [caller, called] means the first rings the second. The list was once a proper chain: every station had exactly one caller except control, which had none, and following the calls back from anywhere ended at control.

One extra line was then typed in, so the list holds n lines for n stations. Strike one line to leave a proper chain again; if more than one would do, strike the one printed lower down.

Input. lines — a list of n pairs [caller, called], in the order printed.

Output. The pair to strike.

Example.

lines = [[3, 1], [3, 2], [1, 4], [2, 4]]   ->  [2, 4]

Station 4 is rung twice, and striking either of its lines leaves a chain under control 3 — so the lower one goes.

A second example, where the loop is not the fault:

lines = [[3, 1], [4, 1], [1, 2], [2, 3]]   ->  [3, 1]

Station 1 is rung twice and the calls also run round 1 → 2 → 3 → 1. Striking the line that closes that loop, [2, 3], still leaves station 1 with two callers. Striking [3, 1] leaves control 4 ringing 1, then 2, then 3.

lines = [[1, 2], [2, 3], [3, 4], [4, 1]]   ->  [4, 1]

Every station has one caller and there is no control at all: the list is a ring, and the last line printed closes it.

Constraints.

• 3 <= n <= 1000, and len(lines) == n
• 1 <= caller, called <= n, with caller != called
• no pair is printed twice
• the list is a proper chain plus exactly one extra line

Hints

Approach

Brute force

Strike each line in turn and check the remaining n - 1 for one control and no ring. Each check is O(n), so the whole thing is O(n²) — a million steps at the top of the range.

The insight

The extra line leaves one of two marks, a station with two callers or a ring, and when both appear the line to strike must be one of that station's two — so hold back the lower one and see whether the tangle goes with it.

If no station is rung twice, the only fault is a ring, and the line that closes it as you read down is the one to strike. If some station is rung twice, the extra line is one of its two by definition. Set the lower aside and merge the rest: no ring means the lower one was the fault, a ring means the upper one was.

Merging ignores direction, and that is safe only because of the hold-back: with the lower line set aside, every station has at most one caller, so the only way the merge can close a ring is along the arrows. Without that guarantee a union-find would report undirected loops that are not rings at all.

Algorithm

1. Read the list once, recording each station's caller. On a station that already has one, remember both lines as early and late.
2. Merge the lines into groups with union-find, skipping late if there is one.
3. If a line joins two stations already in the same group, it closes a ring: answer early when there is one, otherwise that line.
4. If no line closed a ring, answer late.

Complexity

Time O(n α(n)) — two passes over n lines, each doing union-find lookups that are all but constant. Space O(n) for the groups and the caller map.

Solution

"""One call line too many — the extra line is a second caller, a loop, or both."""


def find(group, station):
    while group[station] != station:
        group[station] = group[group[station]]   # halve the path on the way up
        station = group[station]
    return station


def solve(lines):
    stations = len(lines)
    caller = {}
    early = late = None
    for called_by, station in lines:
        if station in caller:
            early, late = [caller[station], station], [called_by, station]
        else:
            caller[station] = called_by

    group = list(range(stations + 1))            # stations are numbered 1..n
    for line in lines:
        if line == late:
            continue                             # held back: try the later line first
        a, b = find(group, line[0]), find(group, line[1])
        if a == b:
            # invariant: every line read so far joined two separate groups, so
            # this one closes the first loop in reading order
            return early if early else line
        group[a] = b

    return late

TESTS = [
    (([[3, 1], [3, 2], [1, 4], [2, 4]],), [2, 4]),
    (([[3, 1], [4, 1], [1, 2], [2, 3]],), [3, 1]),   # a loop that is not the fault
    (([[1, 2], [2, 3], [3, 4], [4, 1]],), [4, 1]),   # a plain ring, one caller each
    (([[2, 3], [2, 1], [3, 1]],), [3, 1]),
    (([[1, 3], [3, 2], [2, 1]],), [2, 1]),
    (([[5, 1], [1, 2], [2, 3], [3, 4], [4, 1]],), [4, 1]),
    (([[1, 2], [2, 3], [3, 1], [5, 4], [4, 1]],), [3, 1]),
]

Pitfalls

• Striking whichever line closes the ring. In the second example that is [2, 3], and striking it leaves station 1 rung twice.
• Striking the first of the two lines on sight. In the first example both leave a proper chain, and the scheme asked for the lower of the two.
• Assuming a twice-rung station always exists. The third example is a plain ring: every station has one caller and the ring is the whole fault.

Variants

• A tunnel to seal — the same extra edge on an undirected map, where "rung twice" is not a thing that can go wrong.
• Cycles and topological order — what a ring costs an ordering, and how a peel finds one.