The trunk line survey

A county telephone company is being sold, and the buyer wants to know how many separate networks it is buying, not how many exchanges.

The problem

The county has n exchanges, numbered 0 to n - 1. The survey arrives as a square table linked. The entry linked[i][j] is 1 when a trunk line runs directly between exchange i and exchange j, and 0 when none does. A trunk carries calls both ways, so the table is symmetric, and every diagonal entry is 1 because an exchange always reaches itself.

A call can be routed between two exchanges when some chain of trunk lines joins them, however long the chain. Exchanges joined that way form one network. An exchange with no trunk at all is a network of one.

Report how many separate networks the table describes.

Input. linked — an n by n list of lists of 0 and 1.

Output. An integer: the number of networks.

Example.

linked = [[1, 1, 0],
          [1, 1, 0],
          [0, 0, 1]]   ->  2

Exchanges 0 and 1 share a trunk. Exchange 2 has none, and still counts.

A second example, where a chain does the work no single trunk does:

linked = [[1, 1, 0, 0],
          [1, 1, 1, 0],
          [0, 1, 1, 0],
          [0, 0, 0, 1]]   ->  2

Nothing runs directly between 0 and 2, but the chain through 1 joins them, so 0, 1 and 2 are one network and exchange 3 is the second.

Constraints.

• 1 <= n <= 200
• linked[i][j] is 0 or 1
• linked[i][j] == linked[j][i] and linked[i][i] == 1

Hints

Approach

Brute force

From each exchange, search the table for everything it reaches, and store the set of exchanges found. Then count the distinct sets. Each search reads up to n² entries, so this is O(n³) — 8 million entry reads at n = 200, plus the cost of comparing 200 sets.

The insight

Start with n networks, and let each trunk line merge two of them, counting only the merges that actually join different groups.

A trunk either joins two groups, which drops the network count by one, or runs between two exchanges already routable to each other, which changes nothing. Deciding which case you are in is exactly the query union-find answers. The precondition holds because trunks are only ever added while the survey is read — nothing is torn out halfway, so a group never splits.

Algorithm

1. Set parent[i] = i for every exchange, and networks = n.
2. Scan only the entries with j > i. The lower triangle repeats the upper one, and the diagonal says nothing.
3. On a 1, find the root of i and the root of j.
4. If the roots differ, attach the smaller group to the larger and subtract one from networks. If they match, move on.
5. Return networks.

Complexity

Time O(n² α(n)), effectively O(n²) — one pass over half the table, with near-constant work per entry. Space O(n): one parent and one size entry per exchange, whatever the trunk count.

Solution

"""The trunk line survey — start with one network per exchange and merge on each trunk."""


def find(parent, x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:               # second pass flattens the path
        parent[x], x = root, parent[x]
    return root


def solve(linked):
    n = len(linked)
    parent = list(range(n))
    size = [1] * n
    networks = n                           # invariant: networks == groups in `parent`

    for i in range(n):
        for j in range(i + 1, n):          # upper triangle only: the table is symmetric
            if not linked[i][j]:
                continue
            ri, rj = find(parent, i), find(parent, j)
            if ri == rj:
                continue                   # already routable: this trunk changes nothing
            if size[ri] < size[rj]:
                ri, rj = rj, ri
            parent[rj] = ri
            size[ri] += size[rj]
            networks -= 1

    return networks

TESTS = [
    (([[1, 1, 0],
       [1, 1, 0],
       [0, 0, 1]],), 2),
    (([[1, 1, 0, 0],
       [1, 1, 1, 0],
       [0, 1, 1, 0],
       [0, 0, 0, 1]],), 2),
    (([[1]],), 1),                          # one exchange is still one network
    (([[1, 0, 0],
       [0, 1, 0],
       [0, 0, 1]],), 3),                    # no trunks at all
    (([[1, 1, 1],
       [1, 1, 1],
       [1, 1, 1]],), 1),                    # three trunks, only two merges
    (([[1, 1, 0, 0, 0, 0],
       [1, 1, 1, 0, 0, 0],
       [0, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 0],
       [0, 0, 0, 1, 1, 1],
       [0, 0, 0, 0, 1, 1]],), 2),
]

Pitfalls

• Subtracting one for every 1 instead of every real merge. A table where 0, 1 and 2 are all directly trunked has three ones above the diagonal and reports 3 - 3 = 0 networks. The right answer is 1.
• Counting the diagonal as a trunk. linked[i][i] is 1 by convention. Merging an exchange with itself is harmless, but subtracting for it takes the count straight to zero.
• Skipping rows whose only 1 is the diagonal. An exchange with no trunk is still a network; drop those rows and the first example reports 1.

Variants

• The mill floor load — the same merging, but the merges are made in a chosen order and one of them is the answer.
• The cask ledger — groups built the same way, then queried by a second list of claims.