Redundant Connection II

TIP103 Unit 7 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 35-45 mins
• 🛠️ Topics: Graphs, Directed Graphs, Union-Find (Disjoint Set), Cycle Detection

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What makes a directed graph a valid rooted tree?

  • There is exactly one root node with no parent, every other node has exactly one parent, and there are no cycles.

• How can adding one extra directed edge break the tree?

  • It can give some node two parents, it can create a cycle, or it can do both at once.

• If more than one edge could be removed to fix the tree, which one do we return?

  • The edge that appears last in the input list.

HAPPY CASE
Input: edges = [[1, 2], [1, 3], [2, 3]]
Output: [2, 3]
Explanation: Node 3 has two parents (1 and 2), but there is no cycle. Removing the later of the two conflicting edges, [2, 3], restores a valid rooted tree.

Input: edges = [[1, 2], [2, 3], [3, 4], [4, 1], [1, 5]]
Output: [4, 1]
Explanation: No node has two parents, but the edges form the cycle 1 -> 2 -> 3 -> 4 -> 1. Removing the edge that closes the cycle, [4, 1], restores a valid rooted tree.

EDGE CASE
Input: edges = [[2, 1], [3, 1], [4, 2], [1, 4]]
Output: [2, 1]
Explanation: Node 1 has two parents (2 and 3) AND the graph contains the cycle 1 -> 4 -> 2 -> 1. Only removing [2, 1] fixes both problems at once, even though [3, 1] appears later in the input.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Directed Graph Validity Problems, we can consider the following approaches:

• Union-Find (Disjoint Set): Merge nodes edge by edge and detect the moment an edge connects two nodes that are already in the same component, which signals a cycle.
• Case Analysis on Parents: A first pass over the edges finds any node with two parents, splitting the problem into three cases: two parents without a cycle, a cycle without two parents, or both.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Make one pass to check whether any node has two parents. If so, call the two conflicting edges cand1 (earlier) and cand2 (later). Then run Union-Find over all edges while skipping cand2. If no cycle appears, cand2 was the redundant edge. If a cycle still appears, then cand1 is the culprit when a two-parent node exists; otherwise (no two-parent node at all) the answer is the edge that closed the cycle.

1) First pass: record each node's parent as edges are read.
   a) If an edge points to a node that already has a parent, save the earlier edge as cand1 and the current edge as cand2.
2) Second pass: run Union-Find over the edges, skipping cand2 if it exists.
   a) For each edge (u, v), find the roots of u and v.
   b) If the roots are equal, a cycle has formed:
      - If no node had two parents (cand1 is None), return the current edge (u, v).
      - Otherwise, return cand1.
   c) Otherwise, union the two components.
3) If the second pass finishes with no cycle, return cand2.

⚠️ Common Mistakes

• Returning cand2 unconditionally whenever a node has two parents, without checking whether skipping cand2 still leaves a cycle (in that case cand1 is the answer).
• Treating the graph as undirected: [1, 2] and [2, 1] are different directed edges, and Redundant Connection I logic does not carry over unchanged.
• Forgetting the tiebreak rule that when multiple answers exist, the edge appearing last in the input must be returned.

4: I-mplement

Implement the code to solve the algorithm.

def find_redundant_directed_connection(edges):
    n = len(edges)

    # Step 1: Look for a node with two parents
    parent_of = [0] * (n + 1)
    cand1 = None  # earlier edge pointing to the doubly-parented node
    cand2 = None  # later edge pointing to the doubly-parented node
    for u, v in edges:
        if parent_of[v]:
            cand1 = [parent_of[v], v]
            cand2 = [u, v]
        else:
            parent_of[v] = u

    # Step 2: Union-Find over all edges, skipping cand2 if it exists
    root = list(range(n + 1))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]  # path compression
            x = root[x]
        return x

    for u, v in edges:
        if [u, v] == cand2:
            continue
        root_u, root_v = find(u), find(v)
        if root_u == root_v:
            # A cycle formed even without cand2
            if cand1 is None:
                return [u, v]  # no two-parent node: the cycle edge is redundant
            return cand1       # two-parent node + cycle: cand1 is the culprit
        root[root_v] = root_u

    # Skipping cand2 removed every problem, so cand2 is the redundant edge
    return cand2

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

  • First pass: node 3 gets parent 1, then edge [2, 3] arrives, so cand1 = [1, 3] and cand2 = [2, 3].
  • Second pass skips [2, 3]: union(1, 2), union(1, 3) succeed with no cycle.
  • Output: [2, 3]

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

  • First pass: every node has at most one parent, so cand1 = cand2 = None.
  • Second pass: union(1, 2), union(2, 3), union(3, 4) succeed; edge [4, 1] finds both endpoints in the same component, and since cand1 is None the cycle edge itself is returned.
  • Output: [4, 1]

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

  • First pass: cand1 = [2, 1], cand2 = [3, 1].
  • Second pass skips [3, 1] but edge [1, 4] still closes a cycle (1 -> 4 -> 2 -> 1), so cand1 is returned.
  • Output: [2, 1]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes (and also the number of edges, since a rooted tree of N nodes plus one extra edge has exactly N edges).

• Time Complexity: O(N * α(N)), effectively O(N), because we make two linear passes over the edges and each Union-Find operation with path compression runs in near-constant amortized time (α is the inverse Ackermann function).
• Space Complexity: O(N) for the parent_of array and the Union-Find root array.