Redundant Connection Problem

Redundant Connection Problem — ExecCode Hard DSA Practice

Solve the Redundant Connection 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

In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The resulting graph is given as a list of edges of size n. Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Examples

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

Constraints

n == edges.length 3 ≤ n ≤ 1000 edges[i].length == 2 1 ≤ ai, bi ≤ n ai != bi

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