Redundant Connection

Find the edge that creates a cycle in an undirected graph.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Redundant Connection: Accept an edge only when its endpoints have different representative roots; otherwise it closes a cycle.

Input and goalFind the edge that creates a cycle in an undirected graph.

Initialize singleton componentsNodes 1..4 each parent themselves and each root has size 1.

node1first2second34parent1234root size1111accepted edgesnone

exampleedges=[[1,2],[3,4],[2,3],[4,2]]currentEdge[1,2]

Recognize it

Undirected edges arrive incrementally and each needs an already-connected cycle check.

Keep true

Following parent links reaches one representative per component; size is authoritative at roots, and accepted edges join only different roots.

Reuse it

Compare roots before adding connectivity, attach the smaller tree under the larger, and compress paths during find.

Pattern: Union-find.

Simple idea: Before adding an edge, check whether both ends already have the same root. If they do, the edge closes a cycle.

class DisjointSet:
   def __init__(self, size: int) -> None:
      self.parent = list(range(size))
      self.component_size = [1] * size

   def find(self, node: int) -> int:
      while node != self.parent[node]:
         self.parent[node] = self.parent[self.parent[node]]
         node = self.parent[node]
      return node

   def union(self, first: int, second: int) -> bool:
      first_root = self.find(first)
      second_root = self.find(second)
      if first_root == second_root:
         return False

      if self.component_size[first_root] < self.component_size[second_root]:
         first_root, second_root = second_root, first_root
      self.parent[second_root] = first_root
      self.component_size[first_root] += self.component_size[second_root]
      return True


def find_redundant_connection(edges: list[list[int]]) -> list[int]:
   if not edges:
      return []

   groups = DisjointSet(max(max(edge) for edge in edges) + 1)
   for first, second in edges:
      if not groups.union(first, second):
         return [first, second]
   return []

Cost: Close to $O(E)$ time and $O(V)$ space.