Redundant Connection II Problem

Redundant Connection II Problem — ExecCode Hard DSA Practice

Solve the Redundant Connection II problem on ExecCode. Free online hard DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A rooted tree is a directed graph where exactly one node has no parent (the root), and every other node has exactly one parent, with no cycles. You are given a rooted tree with n nodes labeled 1 to n, described by edges, where one extra directed edge was added on top of a valid tree. Return an edge that can be removed so the remaining edges form a valid rooted tree with n nodes; if multiple answers exist, return the one that occurs last in the input.

Examples

Input edges = [[1, 2], [1, 3], [2, 3]]; Output [2, 3]. Input edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]; Output [4, 1]. Input edges = [[2, 1], [3, 1], [4, 2], [1, 4]]; Output [2, 1]

Constraints

n == edges.length 3 ≤ n ≤ 1000 edges[i].length == 2 1 ≤ ui, vi ≤ n

Practice Redundant Connection II free on ExecCode. Browse DSA problems, topic map, and placement guides.