Redundant Connection II

Given a directed graph that started as a rooted tree and then received one extra edge, return the edge that should be removed so the graph becomes a rooted tree again. This problem combines union-based cycle detection with parent tracking.

Input Format

edges = directed edges of a rooted tree with one extra edge

Output Format

edge to remove to restore a rooted tree

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

[2,3]

Explanation:

Node 3 has two parents and the later edge [2,3] is removed.

Example 2:

Input:

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

Output:

[4,1]

Explanation:

The directed cycle is closed by edge [4,1].

Example 3:

Input:

edges = [[2,1],[3,1],[4,2],[1,4]]

Output:

[2,1]

Explanation:

Node 1 has two parents and the first conflicting edge is removed.

Loading...
Redundant Connection II - Union Find DSA Problem