Q86: Redundant Connection. - DSA Patterns (Multi-Lang)

In Simple Words: DSU on edge list. For each edge [u, v], check if find(u) === find(v). If both vertices are already in the same connected component, this edge creates a cycle and is the redundant connection!

Time: $O(N \cdot \alpha(N)) \approx O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    parent = list(range(len(edges) + 1))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]
        parent[ru] = rv
    return []