⚡Flashcard Drill➔
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

  1. Add the edges one by one with union-find.
  2. The first edge whose endpoints are already connected is the redundant one.
  3. Processing in input order automatically satisfies the "last occurrence" tie-break, because the redundant edge is exactly the one that closes the cycle.
  4. 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 n parents for 1-indexed nodes: the array needs n + 1 slots.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems