HardDepth-First SearchBreadth-First SearchUnion FindGraph

Redundant Connection II

1 approach, code in every language

A rooted tree is a directed graph where exactly one node is the root (it has no incoming edge) and every other node has exactly one parent, so all edges point away from the root.

You start with such a rooted tree on n nodes labeled 1 to n and add exactly one extra directed edge, forming edges of length n where edges[i] = [u, v] represents a directed edge from u to v.

Return the one edge that can be removed so the remaining graph is a valid rooted tree again. If several edges qualify, return the one that appears last in the input.

Example 1

Input: edges = [[1,2],[1,3],[2,3]]

Output: [2,3]

Node 3 has two parents (1 and 2). Removing [2,3] leaves node 1 as the root with children 2 and 3, a valid tree.

Example 2

Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]

Output: [4,1]

Every node has one parent but the edges 1 -> 2 -> 3 -> 4 -> 1 form a cycle. Removing [4,1] breaks the loop and restores a rooted tree.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i

Union-Find with Two-Parent Detection

Classify the fault as a two-parent conflict, a cycle, or both, then use union-find to pick the removable edge.

Loading animation…

Intuition

Adding one edge to a rooted tree breaks it in exactly one of two ways: some node gains a second parent, or a cycle appears, or both happen at once. First we scan for a node with two incoming edges and remember the earlier candidate A and the later candidate B. Then we union all edges except B (if B exists) and watch for a cycle. If a cycle still forms without B, then B was innocent and the real culprit is A; if no cycle forms, B was the redundant edge. When there is no two-parent conflict at all, the extra edge simply closed a cycle, so the edge that triggers the union conflict is the answer. Processing edges in order and preferring the later candidate handles the tie-breaking rule automatically.

Algorithm walkthrough

1Scan the edges tracking each node's incoming edge index; if a node already has a parent, record candidate A (earlier edge) and candidate B (current edge).
2Initialize a union-find structure over nodes 1..n with path compression.
3Iterate the edges again, skipping candidate B if it exists, and try to union each edge's endpoints.
4If two endpoints already share a root, a cycle exists: return candidate A when a two-parent conflict was found, otherwise return this cycle-closing edge.
5If the loop finishes without any cycle, the skipped candidate B is the redundant edge.
6Return the identified edge, which is guaranteed to be the last valid removable edge.

Implementation

from typing import List

class Solution:
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent_edge = [-1] * (n + 1)
        cand1 = -1
        cand2 = -1
        for i in range(n):
            v = edges[i][1]
            if parent_edge[v] != -1:
                cand1 = parent_edge[v]
                cand2 = i
            else:
                parent_edge[v] = i

        uf = list(range(n + 1))

        def find(x: int) -> int:
            while uf[x] != x:
                uf[x] = uf[uf[x]]
                x = uf[x]
            return x

        for i in range(n):
            if i == cand2:
                continue
            u, v = edges[i]
            ru, rv = find(u), find(v)
            if ru == rv:
                return edges[cand1] if cand1 != -1 else edges[i]
            uf[rv] = ru

        return edges[cand2]

Time

O(n * alpha(n))

Space

O(n)

Two linear passes over the edges with near-constant amortized union-find operations; the arrays use O(n) space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free