Solutions

# DFS cycle detection, topological sort, and Disjoint Set Union (Union-Find).
# graphs

# DFS cycle detection - O(E * (V+E)) time, O(V+E) space
def findRedundantConnection1(edges: list[list[int]]) -> list[int]:
    N = len(edges) # a tree with N nodes has N-1 edges, so we have N edges here since one is redundant
    adj = {i: [] for i in range(N+1)}

    def dfs(n: int, parent: int, visited: set) -> bool:
        if n in visited:
            return False

        visited.add(n) 
        for a in adj[n]:
            if a == parent:
                continue
            if not dfs(a, n, visited):
                return False
        return True

    # Add edges one by one and check if there's a loop
    for u,v in edges:
        # Undirected graph, so we add both
        adj[u].append(v)
        adj[v].append(u)

        if not dfs(u, -1, set()):
            return [u, v]

    return []

# Topological sort (Kahn's algorithm) - O(V+E) time, O(V+E) space
def findRedundantConnection2(edges: list[list[int]]) -> list[int]:
    N = len(edges)
    indegree = {i: 0 for i in range(N+1)}
    adj = {i: [] for i in range(N+1)}

    for u,v in edges:
        indegree[u] += 1
        indegree[v] += 1
        adj[u].append(v)
        adj[v].append(u)

    from collections import deque
    q = deque()
    # Add all nodes with degree 1 (leaf nodes) to the queue
    for node, degree in indegree.items():
        if degree == 1:
            q.append(node)

    while q:
        n = q.popleft()
        indegree[n] -= 1

        for nei in adj[n]:
            indegree[nei] -= 1
            if indegree[nei] == 1:
                q.append(nei)

    for u,v in reversed(edges):
        if indegree[u] > 0 and indegree[v] > 0:
            return [u,v]
    return []


# Disjoint Set Union (Union-Find) - O(V + E * α(V)) time, O(V) space,
# where α is the inverse Ackermann function, which is very slow growing and can be considered almost constant for all practical purposes.
def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    dsu = DSU(len(edges)+1)
    
    for u,v in edges:
        if not dsu.union(u,v):
            return [u, v]

    return []
        

# Disjoint Set Union (Union-Find) solution
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n)) # [0, 1, 2, ..., n-1]
        self.rank = [1] * n

    def find(self, x: int) -> int:
        """Find the root of the component/set that x belongs to, with path compression."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """Union the sets that x and y belong to. Return True if merged, False if already in the same set."""
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x == root_y:
            return False  # They are already in the same set

        # Union by rank
        if self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        elif self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1

        return True