NeetCode #583LC-684MediumGraphsNC 150NC 250
← Back to All Problems#583 · #684 · Redundant Connection(冗余连接)
📌 Problem Statement & Constraints
In a graph that started as a tree with
n nodes and one extra edge was added, given the edges list, return the extra edge. If there are several answers, return the one that occurs last in the input. Constraints: 3 <= n <= 1000, edges.length == n.💡 Core Algorithmic Approaches
- Add the edges one by one with union-find.
- The first edge whose endpoints are already connected is the redundant one.
- Processing in input order automatically satisfies the "last occurrence" tie-break, because the redundant edge is exactly the one that closes the cycle.
- Since exactly one edge is extra, the answer is unique in this formulation.
💻 Benchmark Python3 Implementation
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
parent = list(range(n + 1)) # nodes are 1-indexed
def find(x: int) -> int:
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] # this edge closes a cycle
parent[ra] = rb
return []⚡ Complexity Deep Dive
⏱️ Time Complexity
O(E * alpha(V)): effectively linear.
💾 Space Complexity
O(V) for the parent array.
⚠️ Interview Pitfalls & Follow-ups
- Sorting the edges first: the input order defines the tie-break.
- Allocating
nparents for 1-indexed nodes: the array needsn + 1slots. - Trying to detect the cycle with a DFS per edge: O(V * E).
- Returning the first edge in the cycle found by a DFS: it may not be the last one in the input.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.