LeetCode 684 · Graphs

Redundant Connection, explained with a picture

The one cable too many.

MediumGraphs
▶ Watch it step by step

The problem

A network started as a tree (connected, no loops) and then one extra edge was added. Find that edge: the one that creates a loop. If several could be removed, return the one that appears last in the input.

Input:  cables 1-2, 2-3, 3-4, 1-4, 1-5
Output: [1, 4]

Picture it

Picture laying network cables between computers one at a time. We keep track of which computers are already in the same connected group (a union-find). If a new cable connects two computers that are already in the same group, it’s redundant: it closes a loop.

How to recognise it

  • An undirected graph that was a tree until one extra edge was added, and you must name that edge.
  • The extra edge is the one that joins two nodes that were already connected.
  • Edges can be handled one at a time in input order, and the answer is the first edge that closes a loop.
  • n is up to 1,000 here, but the same idea works for 10^5 edges where repeated graph searches are too slow.

Start with brute force

Try removing each edge, starting from the last. If what remains is a tree (connected, with n − 1 edges), the removed edge was redundant, and because we start from the end it is the one that appears last.

def find_redundant_brute(edges):
    n = len(edges)
    def is_tree(es):
        adj = defaultdict(list)
        for a, b in es:
            adj[a].append(b); adj[b].append(a)
        seen, st = {1}, [1]
        while st:
            x = st.pop()
            for y in adj[x]:
                if y not in seen:
                    seen.add(y); st.append(y)
        return len(seen) == n
    for i in range(n - 1, -1, -1):
        if is_tree(edges[:i] + edges[i + 1:]):
            return edges[i]

Each candidate costs a graph search of O(V + E) plus building a new list, and there are E candidates, so time is O(E·(V + E)). With 1,000 edges that is about 2 × 10^6 steps, fine here, but at 10^5 edges it is about 2 × 10^10. Space is O(V + E).

From brute force to the idea

  1. Find the waste. Every candidate removal re-searches the whole graph, but the graph is almost identical each time.
  2. Add edges one at a time and track groups. Each node starts alone. Joining two nodes merges their groups.
  3. Union-find stores the groups. parent[x] points towards a group's representative, and find(x) follows the pointers to the root. The line parent[x] = parent[parent[x]] is path halving: it shortens the chain each time it is walked.
  4. Read the answer off the merge. For each edge, if the two roots are different, link one root under the other. If they are already equal, the two nodes were connected, so this edge closes a loop: return it.
  5. Why it is the last edge. Edges are processed in order, so the first edge that finds both ends already connected is the last edge of the cycle in the input.

The key idea: an edge whose ends already share a root is the redundant one.

The key idea

Union-find: for each edge, if find(a) == find(b) it is the extra edge; otherwise union them.

Python solution

def find_redundant(edges):
    n = len(edges) + 1
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]   # closes a loop
        parent[rb] = ra

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(E·(V + E)): a full search for each candidate edgeO(V + E): adjacency lists and a seen set
Union-find (shown code)O(E log V) at worst, and close to O(E) in practice, because path halving keeps chains short (no union by size is used)O(V): the parent list of n + 1 entries

Edge cases

  • Smallest case ([[1,2],[1,3],[2,3]]): returns [2, 3].
  • The loop closes before all nodes appear ([[1,2],[2,3],[1,3],[3,4]]): returns [1, 3]. The extra edge is not always last in the input.
  • Cycle edges in any order ([[1,2],[2,3],[3,1]]): returns [3, 1], the one that comes last.
  • Node labels start at 1. The parent list has n + 1 entries (indices 0 to n, with 0 unused), where n is len(edges).
  • Input that is not "tree plus one edge": the function returns None if no edge closes a loop, and fails with an index error if a label exceeds len(edges).

Common mistakes

  • Building parent with only len(edges) entries, so the largest label is out of range.
  • Linking the nodes instead of their roots (parent[b] = a), which can break earlier merges.
  • Returning the edge as [b, a] or sorting it, when the answer must match the input order.
  • Using a graph search per edge, which is correct but too slow for large inputs.
  • Applying Kahn's topological sort, which is for directed graphs.
Your turn: count the extras

The graph is now arbitrary: n nodes labelled 0 to n − 1 and any edges, possibly several loops. Return how many edges are redundant, meaning how many edges join two nodes already connected when they are added. Describe what changes, then write it if you like.

Compare with our answer

Run the same union-find, but instead of returning at the first repeat, count each one.

def count_redundant(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    extra = 0
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            extra += 1
        else:
            parent[rb] = ra
    return extra

count_redundant(3, [[0,1],[0,1],[2,2]]) is 2: the repeated edge and the self-loop. The answer equals the number of edges minus (n minus the number of groups). Time O(E log V), space O(V).

A strong answer mentions: continuing after a repeat instead of returning, that self-loops and duplicates count, and the link to the number of components.

Check what stuck

1. An undirected graph with 10^5 edges arrives as a list. You must tell whether it contains any cycle at all. Which approach fits best?

2. What does it mean when find(a) == find(b) for the next edge (a, b)?

3. A learner changes n = len(edges) + 1 to n = len(edges). Which input still returns the right answer?

Score 60% or more and the lesson is marked complete.