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
- Find the waste. Every candidate removal re-searches the whole graph, but the graph is almost identical each time.
- Add edges one at a time and track groups. Each node starts alone. Joining two nodes merges their groups.
- Union-find stores the groups.
parent[x]points towards a group's representative, andfind(x)follows the pointers to the root. The lineparent[x] = parent[parent[x]]is path halving: it shortens the chain each time it is walked. - 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.
- 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] = raIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(E·(V + E)): a full search for each candidate edge | O(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
parentlist has n + 1 entries (indices 0 to n, with 0 unused), where n islen(edges). - Input that is not "tree plus one edge": the function returns
Noneif no edge closes a loop, and fails with an index error if a label exceedslen(edges).
Common mistakes
- Building
parentwith onlylen(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.
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.
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?
Each edge either joins two groups or finds both ends already together, which means a cycle. Kahn's algorithm is for directed graphs. Sorting and prefix searches do not detect cycles efficiently.
2. What does it mean when find(a) == find(b) for the next edge (a, b)?
Equal roots mean one group, so there is already a path between a and b and the new edge adds a second one. The edge need not be a duplicate: a long path can connect them.
3. A learner changes n = len(edges) + 1 to n = len(edges). Which input still returns the right answer?
Labels go up to n, so parent needs n + 1 entries. The first three inputs touch label n before the loop closes and fail with an index error. In the last one the loop closes at the third edge, before label 4 is touched.
Score 60% or more and the lesson is marked complete.