The Question

Redundant Connection in Directed Graph

Given a directed graph that was originally a rooted tree but now contains one additional directed edge, identify the edge that should be removed to restore its rooted tree structure. If multiple edges could be removed to satisfy this condition, return the one that appears latest in the input sequence.

Java

Union-Find

Graph

DFS

Questions & Insights

Clarifying Questions

What is the maximum value of

n

umber of nodes/edges)? (Assuming

n \le 1000

based on standard competitive programming constraints for this problem).

Are the node values always a continuous range from

1

n

? (Assuming yes, as per the problem description).

Can the added edge create a self-loop (e.g.,

[1, 1]

)? (The problem states

u

and

v

are different, so no self-loops).

Is it guaranteed that the input always contains exactly one redundant edge that, when removed, results in a valid rooted tree? (Assuming yes).

Assumptions

The graph has

n

odes and edges (since a tree has

n-1

edges and one was added).

We need to handle two main violations: a node having two parents and the existence of a directed cycle.

Thinking Process

Identify Violations: In a rooted tree, every node has exactly one parent except the root. Adding an edge can either:

Create a node with two parents (in-degree = 2).

Create a directed cycle.

Create both (a node with two parents where one of the incoming edges is part of a cycle).

Candidate Edges: If a node has two parents, the two edges pointing to it are the only candidates for removal. If no node has two parents, any edge forming a cycle is a candidate.

Cycle Detection: Use a Disjoint Set Union (DSU) to detect cycles. Since the graph is "almost" a tree, if we process edges and find an edge

[u, v]

where

u

and

v

are already in the same component, that edge completes a cycle.

Decision Logic:

If a node has two parents:

Temporarily "hide" the second edge. If the remaining edges form a cycle, the first edge was the problem. Otherwise, the second edge is the answer.

If no node has two parents:

The answer is simply the edge that completes the cycle in the DSU.

Implementation Breakdown

Problem Set

Functional Requirements: Find and return the last edge in the input array whose removal results in a valid rooted tree.

Constraints:

n

odes, edges, directed graph,

O(n \alpha(n))

time complexity preferred.

Approach

Algorithm: Disjoint Set Union (DSU) with Path Compression and Union by Rank + In-degree tracking.

Data Structure: Array for parent pointers (DSU) and an array for in-degree tracking.

Complexity:

Time:

O(n \alpha(n))

, where

\alpha

is the inverse Ackermann function.

Space:

O(n)

to store DSU and parent relationships.

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: While tracking in-degrees and using DSU is efficient, one could also solve this by performing a DFS to check for cycles after removing each candidate edge. However, DFS would be

O(n^2)

in the worst case, making DSU the superior choice for performance.

Handling Multi-roots: This logic assumes

n

edges and

n

odes. If the graph has fewer edges or different constraints, a "forest" might be formed, requiring a more complex check for a single root.

In-place modifications: The code modifies the input edges array (setting edge[1] = 0) to save space. In a production environment, it is better to use a boolean flag or a temporary list to avoid side effects on input data.