Extra Directed Edge Problem

Extra Directed Edge Problem — ExecCode Hard DSA Practice

Solve the Extra Directed Edge problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A directed graph on nodes 1..n should have been a rooted tree (every node indegree 1 except the root). Someone added one extra directed edge. Return that extra edge. If several edges could be the extra, return the one that occurs last in the input among valid candidates (standard OA contract: prefer the edge that creates a two-parent node if that restores a tree). Return the redundant directed edge [u, v]. You are given: edges — list of [u,v] directed edges, length n (one extra) Return one edge [u, v]. Handle three shapes: a cycle with a two-parent node, a cycle with a proper tree plus back edge, and two parents without a cycle.

Examples

Input {'edges': [[1, 2], [1, 3], [2, 3]]}; Output [2, 3]. Input {'edges': [[1, 2], [2, 3], [3, 1], [1, 4]]}; Output [3, 1]. Input {'edges': [[2, 1], [3, 1], [4, 2], [1, 4]]}; Output [2, 1]

Constraints

Nodes are 1-indexed Exactly one extra edge exists

Practice Extra Directed Edge free on ExecCode. Browse DSA problems, topic map, and placement guides.