#685

Redundant Connection II

master · 1830 · lc hard +32 · verified · 35.9% accepted · 2,514 likes · top 14%

Description

A rooted tree is a directed graph with exactly one root node (no incoming edges) where every other node has exactly one parent. A rooted tree on n nodes labeled 1 through n was given one extra directed edge. The resulting graph is provided as a 2D array edges, where each element [ui, vi] is a directed edge from parent ui to child vi.

Return an edge that, when removed, restores the graph to a valid rooted tree of n nodes. Among valid answers, return the one appearing 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],[4,1],[1,5]]

Output: [4,1]

Code

1

2

3

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

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