#684

Redundant Connection

specialist · 600 · lc medium +29 · verified · 67.3% accepted · 7,138 likes · top 73%

Description

A tree is an undirected, connected, acyclic graph. Starting from a tree on n nodes labeled 1 through n, one extra edge was inserted between two nodes that were not yet directly connected. The resulting graph is given as an array edges of length n, where edges[i] = [ai, bi] denotes an undirected edge.

Identify and return an edge whose removal restores the graph to a valid tree. If multiple valid answers exist, return the one that appears last in the input.

Example 1:

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

Output: [2,3]

Example 2:

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

Output: [1,4]

Code

1

2

3

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: