FastPrep
Problem · Graph

Redundant Connection II

Learn this problem
● HardAnyscale logoAnyscaleFULLTIMEPHONE SCREEN

Problem statement

A rooted tree is a directed graph in which exactly one node is the root and every other node has exactly one parent. The graph started as a rooted tree with nodes labeled from 1 to n, then one extra directed edge was added.

You are given the resulting directed edges in their original order. Remove one edge so the remaining graph is a rooted tree and return that edge. If more than one removal works, return the valid edge that appears last in the input.

Function

findRedundantDirectedConnection(edges: int[][]) → int[]

Examples

Example 1

edges = [[1,2],[1,3],[2,3]]return = [2,3]

Node 3 has two parents. Removing [2,3] restores the rooted tree.

Example 2

edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]return = [4,1]

The edge [4,1] closes a directed cycle. Removing it leaves node 1 as the root.

Example 3

edges = [[2,1],[3,1],[4,2],[1,4]]return = [2,1]

Node 1 has two parents. Keeping [3,1] and removing [2,1] is necessary because the other candidate participates in the cycle.

Constraints

  • 3 <= edges.length <= 100000.
  • edges[i].length == 2.
  • 1 <= edges[i][0], edges[i][1] <= edges.length.
  • No directed edge appears more than once.
  • The input can be made into a rooted tree by removing exactly one edge.
drafts saved locally
public int[] findRedundantDirectedConnection(int[][] edges) {
  // write your code here
}
edges[[1,2],[1,3],[2,3]]
expected[2,3]
checking account