Redundant Connection II

HardGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A **rooted tree** is a directed graph with exactly one root (a node with no incoming edge), where every other node has exactly one parent and every node is reachable from the root. You are given edges, a list of n directed edges [parent, child] over nodes 1 to n. The graph was a rooted tree on those n nodes, and then **one extra directed edge** was added between two different nodes that were not already connected by that same directed edge. Return an edge that can be removed so the remaining n - 1 edges form a rooted tree over all n nodes. If several edges work, return the one that appears **last** in edges.

Examples

Input: edges = [[1,2],[2,3],[3,4],[4,2]]
Output: [4,2]
Node 2 has two parents. Removing `[4,2]` leaves the tree 1 -> 2 -> 3 -> 4. Removing `[1,2]` instead would leave the cycle 2 -> 3 -> 4 -> 2.
Input: edges = [[2,1],[3,2],[1,3],[4,1]]
Output: [2,1]
Node 1 has parents 2 and 4. Only removing `[2,1]` works (root 4), even though `[4,1]` appears later.
Input: edges = [[1,2],[2,3],[3,1],[1,4]]
Output: [3,1]
No node has two parents; the cycle 1 -> 2 -> 3 -> 1 has no root. Any cycle edge works, and `[3,1]` is the last of them.

Constraints

  • `n == edges.length`
  • `3 <= n <= 1000`
  • `1 <= parent_i, child_i <= n`
  • `parent_i != child_i`
  • The input is a rooted tree plus one extra edge, as described

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems