DSA Redundant Connection

The problem

Redundant Connection gives the edges of a graph on vertices 1 to n. The graph was a tree until exactly one extra edge was added.

A tree connects every vertex with no cycle. The extra edge closes exactly one cycle. The answer is that extra edge, printed as given.

cases = [
    (3, [[1, 2], [1, 3], [2, 3]], [2, 3]),
    (5, [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]], [1, 4]),
    (4, [[1, 2], [2, 3], [3, 4], [4, 2]], [4, 2]),
]
for n, edges, expected in cases:
    print("n", n, "edges", edges, "-> extra:", expected)

The second graph hides its extra edge in the middle of the list. A leaf edge to vertex 5 closes the list instead. Position alone never gives the answer.

Intuition: take the last edge

The first guess blames the last edge. The guess sounds safe, because the extra edge was added last to the tree. The edge list, though, arrives in any order.

edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
print("last edge:", edges[-1])
degree = {}
for a, b in edges:
    degree[a] = degree.get(a, 0) + 1
    degree[b] = degree.get(b, 0) + 1
print("degree of vertex 5:", degree[5])
print("answer: [1, 4]")

Vertex 5 has degree one, so its only edge is a leaf edge. Removing it would strand vertex 5. The extra edge must sit on the cycle, wherever the list puts it.

Brute force: look for a path between the ends

The brute force adds edges one at a time. Before adding an edge, it searches the graph built so far for a path between the edge's ends. A path that already exists makes the new edge redundant.

from collections import deque

def find_brute(n, edges):
    graph = {i: [] for i in range(1, n + 1)}
    visits = 0
    for a, b in edges:
        seen = {a}
        queue = deque([a])
        found = False
        while queue:
            node = queue.popleft()
            visits += 1
            if node == b:
                found = True
                break
            for nxt in graph[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
        if found:
            return [a, b], visits
        graph[a].append(b)
        graph[b].append(a)
    return None, visits

for n, edges in ((3, [[1, 2], [1, 3], [2, 3]]), (5, [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])):
    edge, visits = find_brute(n, edges)
    print("extra edge:", edge, "path-search visits:", visits)

The search repeats for every edge, and each search can walk the whole graph built so far. The visit counter shows the repeated walking.

The optimal solution: union the ends, watch for a refusal

Union-find keeps the connected groups, and the first edge whose ends already share a group is the extra edge. That one sentence is the whole method.

A union that merges two groups adds a tree edge. A union that finds its ends together adds nothing and closes the cycle instead. Testing stops at that edge.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def find_redundant(n, edges):
    uf = UnionFind(n)
    checked = 0
    for a, b in edges:
        checked += 1
        if not uf.union(a, b):
            return [a, b], checked
    return None, checked

cases = [
    (3, [[1, 2], [1, 3], [2, 3]], [2, 3]),
    (5, [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]], [1, 4]),
    (4, [[1, 2], [2, 3], [3, 4], [4, 2]], [4, 2]),
]
for n, edges, expected in cases:
    edge, checked = find_redundant(n, edges)
    print("extra:", edge, "edges checked:", checked, "match:", edge == expected)

All three cases pass. The second answer arrives at the fourth edge, and the fifth edge is never tested.

Walkthrough: groups on the second graph

Five vertices start as five single groups. Each union below merges two groups into one. The groups print after every successful edge.

parent = list(range(6))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]
for a, b in edges:
    ra, rb = find(a), find(b)
    if ra == rb:
        print("edge", [a, b], "- ends already share root", ra, "-> redundant")
        break
    parent[rb] = ra
    groups = {}
    for v in range(1, 6):
        groups.setdefault(find(v), []).append(v)
    print("edge", [a, b], "- groups:", sorted(groups.values()))

Three unions grow one group of four vertices. The edge from 1 to 4 then finds both ends inside that group. The walk stops there, with the answer in hand.

Complexity

The brute force searches a path for every edge, so its visits grow with the edges times the vertices. Union-find does one find per end, so its work grows with the edge count alone.

Both store one entry per vertex or edge. The brute force keeps an adjacency list and union-find keeps a parent array, each O(n).

from collections import deque

def brute_visits(n, edges):
    graph = {i: [] for i in range(1, n + 1)}
    visits = 0
    for a, b in edges:
        seen = {a}
        queue = deque([a])
        found = False
        while queue:
            node = queue.popleft()
            visits += 1
            if node == b:
                found = True
                break
            for nxt in graph[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
        if found:
            return visits
        graph[a].append(b)
        graph[b].append(a)
    return visits

def union_finds(n, edges):
    parent = list(range(n + 1))
    finds = 0

    def find(x):
        nonlocal finds
        finds += 1
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return finds
        parent[rb] = ra
    return finds

for n in (5, 9, 17):
    edges = [[i, i + 1] for i in range(1, n)] + [[1, n]]
    print("vertices", n, "- brute visits:", brute_visits(n, edges), " union finds:", union_finds(n, edges))

At 17 vertices the brute force pays 153 visits against 50 finds. The gap widens with every vertex added, because each path search rewalks the whole graph built so far.

Edge cases and pitfalls

Three vertices make the smallest possible cycle. The closing edge is the third one, and no smaller graph can hold a cycle at all.

Edges after the answer change nothing. A trailing leaf edge is never even tested, because the search stops at the first refusal.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def find_redundant(n, edges):
    uf = UnionFind(n)
    checked = 0
    for a, b in edges:
        checked += 1
        if not uf.union(a, b):
            return [a, b], checked
    return None, checked

print("triangle:", find_redundant(3, [[1, 2], [2, 3], [1, 3]])[0])
print("trailing leaf edge:", find_redundant(4, [[1, 2], [2, 3], [1, 3], [3, 4]]))
print("pure tree:", find_redundant(3, [[1, 2], [2, 3]])[0])

The pure tree prints None. The problem promises one extra edge, so that case never arrives in valid input. The code still answers sanely instead of crashing.