# Redundant Connection II
**Difficulty:** HARD
[External](https://leetcode.com/problems/redundant-connection-ii)
Canonical: https://scaleengineer.com/dsa/problems/redundant-connection-ii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## Problem
In this problem, a rooted tree is a **directed** graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with `n` nodes (with distinct values from `1` to `n`), with one additional directed edge added. The added edge has two different vertices chosen from `1` to `n`, and was not an edge that already existed.

The resulting graph is given as a 2D-array of `edges`. Each element of `edges` is a pair `[ui, vi]` that represents a **directed** edge connecting nodes `ui` and `vi`, where `ui` is a parent of child `vi`.

Return _an edge that can be removed so that the resulting graph is a rooted tree of_ `n` _nodes_. If there are multiple answers, return the answer that occurs last in the given 2D-array.

**Example 1:**

![](https://assets.glich.co/dsa/redundant-connection-ii/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/redundant-connection-ii/image1.jpg) 

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

**Constraints:**

* `n == edges.length`
* `3 <= n <= 1000`
* `edges[i].length == 2`
* `1 <= ui, vi <= n`
* `ui != vi`

# Approaches
## Brute Force by Removing Each Edge
This approach involves iterating through each edge, one by one, and checking if its removal results in a valid rooted tree. To satisfy the problem's requirement of returning the last edge in the array in case of multiple possibilities, the iteration is performed in reverse order, from the last edge to the first. The first edge found that validates the tree structure upon removal is the answer.
**Time:** O(N^2). The main loop runs N times. Inside the loop, the validation function builds an adjacency list and performs a graph traversal, both of which take O(N) time. This results in a total time complexity of O(N * N). · **Space:** O(N), where N is the number of nodes. This space is used for the adjacency list, parent count array, and visited set within the validation function.
**Pros:** Conceptually simple and straightforward to implement.; Guaranteed to find the correct answer due to its exhaustive nature.
**Cons:** High time complexity of O(N^2), which may be too slow for larger constraints.; Redundant computations, as graph properties are recalculated from scratch in each iteration.
### Explanation
The core of this method is a helper function that validates if a given graph is a rooted tree. This function is called for each potential subgraph formed by removing one edge.

To check if a graph is a valid rooted tree with `n` nodes and `n-1` edges, we verify the following properties:
1.  **Parent Uniqueness**: We calculate the in-degree for every node. A valid rooted tree must have exactly one node with an in-degree of 0 (the root), and all other `n-1` nodes must have an in-degree of 1. If any node has an in-degree greater than 1, or if there isn't exactly one root, the graph is invalid.
2.  **Connectivity and Acyclicity**: If the parent uniqueness condition holds, we have a potential root. We then perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from this root. If the traversal visits all `n` nodes exactly once, it confirms the graph is connected and contains no cycles. 

The main function iterates from the last edge to the first. For each edge, it constructs a temporary graph excluding that edge and calls the validation logic. The first edge that passes the check is returned.

```java
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        for (int i = n - 1; i >= 0; i--) {
            if (isTreeAfterRemoval(edges, i, n)) {
                return edges[i];
            }
        }
        return new int[0]; // Should not be reached
    }

    private boolean isTreeAfterRemoval(int[][] edges, int edgeToSkip, int n) {
        java.util.List<java.util.List<Integer>> adj = new java.util.ArrayList<>();
        int[] parentCount = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            adj.add(new java.util.ArrayList<>());
        }

        for (int j = 0; j < n; j++) {
            if (j == edgeToSkip) continue;
            int u = edges[j][0];
            int v = edges[j][1];
            adj.get(u).add(v);
            parentCount[v]++;
        }

        int root = -1;
        for (int j = 1; j <= n; j++) {
            if (parentCount[j] == 0) {
                if (root != -1) return false; // More than one root
                root = j;
            } else if (parentCount[j] > 1) {
                return false; // A node has more than one parent
            }
        }
        if (root == -1) return false; // No root found (implies a cycle)

        // Check connectivity from the root
        java.util.Queue<Integer> q = new java.util.LinkedList<>();
        java.util.Set<Integer> visited = new java.util.HashSet<>();
        q.add(root);
        visited.add(root);
        
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (visited.contains(v)) return false; // Cycle detected
                visited.add(v);
                q.add(v);
            }
        }
        
        return visited.size() == n; // All nodes must be reachable
    }
}
```
### Algorithm
- Iterate through each edge in the `edges` array, from the last to the first.
- For each edge, temporarily remove it from the graph.
- Check if the remaining `n-1` edges form a valid rooted tree.
- A graph is a valid rooted tree if:
  1. It has a single root node (a node with an in-degree of 0).
  2. All other `n-1` nodes have an in-degree of exactly 1.
  3. The graph is connected and acyclic. This can be verified by starting a traversal (like BFS or DFS) from the root and ensuring all `n` nodes are visited exactly once.
- The first edge (iterating from the end) whose removal satisfies these conditions is the answer.

## Optimized Approach using Union-Find
This efficient approach correctly identifies the redundant edge by analyzing the structure of the graph. The addition of an extra edge to a rooted tree can create two types of structural violations: a node having two parents, or the formation of a cycle. This algorithm first checks for a two-parent node. Based on whether one is found, it intelligently uses a Union-Find (Disjoint Set Union) data structure to pinpoint the redundant edge in near-linear time.
**Time:** O(N * α(N)), where N is the number of edges and α(N) is the very slow-growing Inverse Ackermann function. For all practical purposes, the complexity is considered linear, O(N). · **Space:** O(N), where N is the number of nodes. This space is required for the `parent` array used in the initial scan and for the internal array of the Union-Find data structure.
**Pros:** Highly efficient with a near-linear time complexity.; Systematically handles all possible scenarios by categorizing the problem.; Avoids expensive graph traversals inside a loop.
**Cons:** The logic is more complex to understand and implement compared to the brute-force approach.; Requires familiarity with the Union-Find data structure.
### Explanation
The problem can be broken down into three distinct scenarios that our algorithm must handle:
1.  **Cycle Only**: The added edge creates a cycle, but no node ends up with two parents. This happens when the new edge points to the original root of the tree.
2.  **Two Parents, No Cycle**: The added edge points to a non-root node, giving it a second parent, but this addition does not create a cycle.
3.  **Two Parents and a Cycle**: The added edge both creates a cycle and results in a node having two parents.

The algorithm elegantly handles all three cases:

```java
class Solution {
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        int[] cand1 = null;
        int[] cand2 = null;

        // Step 1: Check for a node with two parents
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            if (parent[v] != 0) {
                cand1 = new int[]{parent[v], v}; // First edge
                cand2 = new int[]{u, v};          // Second edge
                break;
            }
            parent[v] = u;
        }

        DSU dsu = new DSU(n);

        if (cand1 == null) {
            // Case 1: No node with two parents, so there must be a cycle.
            for (int[] edge : edges) {
                if (!dsu.union(edge[0], edge[1])) {
                    return edge; // This edge forms the cycle
                }
            }
        } else {
            // Case 2 or 3: A node has two parents.
            for (int[] edge : edges) {
                // Skip the second candidate edge to test for a cycle without it
                if (edge[0] == cand2[0] && edge[1] == cand2[1]) {
                    continue;
                }
                if (!dsu.union(edge[0], edge[1])) {
                    // A cycle exists even without cand2, so cand1 must be the culprit.
                    return cand1; // Case 3
                }
            }
            // No cycle found without cand2, so removing it is the solution.
            return cand2; // Case 2
        }
        
        return new int[0]; // Should not be reached
    }
}

class DSU {
    private int[] root;

    public DSU(int n) {
        root = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            root[i] = i;
        }
    }

    public int find(int i) {
        if (root[i] == i) {
            return i;
        }
        return root[i] = find(root[i]);
    }

    public boolean union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            root[rootI] = rootJ;
            return true;
        }
        return false;
    }
}
```
### Algorithm
- **Step 1: Detect Two-Parent Node.** Iterate through the edges and use a `parent` array to track the parent of each node. If an edge `(u, v)` is found where `v` already has a parent, this indicates `v` has two parents. Store the two edges leading to `v` as candidates: `cand1` (the first one found) and `cand2` (the current one).
- **Step 2: Handle Cases.**
  - **Case A (No Two-Parent Node):** If the first step completes without finding any node with two parents, the graph must contain a cycle. Initialize a Union-Find data structure. Process each edge `(u, v)` with the `union` operation. The edge that connects two nodes already in the same set is the one that forms the cycle and is the answer.
  - **Case B (Two-Parent Node Exists):** We have two candidate edges, `cand1` and `cand2`. The goal is to determine which one to remove. We test the graph's integrity by temporarily ignoring `cand2`. We initialize a Union-Find structure and process all edges *except* `cand2`.
    - If a cycle is detected during this process, it means the cycle exists independently of `cand2`. Therefore, `cand1` must be part of that cycle, and removing it is the correct action to fix both the cycle and the two-parent issue. Return `cand1`.
    - If no cycle is detected, it means removing `cand2` is sufficient to make the graph a valid tree (acyclic with correct parent counts). Return `cand2`.

# Solutions
### Java

```java
class Solution {
public
  int[] findRedundantDirectedConnection(int[][] edges) {
    int n = edges.length;
    int[] p = new int[n + 1];
    for (int i = 0; i <= n; ++i) {
      p[i] = i;
    }
    UnionFind uf = new UnionFind(n + 1);
    int conflict = -1, cycle = -1;
    for (int i = 0; i < n; ++i) {
      int u = edges[i][0], v = edges[i][1];
      if (p[v] != v) {
        conflict = i;
      } else {
        p[v] = u;
        if (!uf.union(u, v)) {
          cycle = i;
        }
      }
    }
    if (conflict == -1) {
      return edges[cycle];
    }
    int v = edges[conflict][1];
    if (cycle != -1) {
      return new int[]{p[v], v};
    }
    return edges[conflict];
  }
} class UnionFind {
public
  int[] p;
public
  int n;
public
  UnionFind(int n) {
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    this.n = n;
  }
public
  boolean union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa == pb) {
      return false;
    }
    p[pa] = pb;
    --n;
    return true;
  }
public
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} edges * @return {number[]} */ var findRedundantDirectedConnection = function ( edges ) { const n = edges . length ; const ind = Array ( n ). fill ( 0 ); for ( const [ _ , v ] of edges ) { ++ ind [ v - 1 ]; } const dup = []; for ( let i = 0 ; i < n ; ++ i ) { if ( ind [ edges [ i ][ 1 ] - 1 ] === 2 ) { dup . push ( i ); } } const p = Array . from ({ length : n }, ( _ , i ) => i ); const find = x => { if ( p [ x ] !== x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; }; if ( dup . length ) { for ( let i = 0 ; i < n ; ++ i ) { if ( i === dup [ 1 ]) { continue ; } const [ pu , pv ] = [ find ( edges [ i ][ 0 ] - 1 ), find ( edges [ i ][ 1 ] - 1 )]; if ( pu === pv ) { return edges [ dup [ 0 ]]; } p [ pu ] = pv ; } return edges [ dup [ 1 ]]; } for ( let i = 0 ; ; ++ i ) { const [ pu , pv ] = [ find ( edges [ i ][ 0 ] - 1 ), find ( edges [ i ][ 1 ] - 1 )]; if ( pu === pv ) { return edges [ i ]; } p [ pu ] = pv ; } };
```

### CPP

```cpp
class UnionFind { public: vector < int > p ; int n ; UnionFind ( int _n ) : n ( _n ) , p ( _n ) { iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) return false ; p [ pa ] = pb ; -- n ; return true ; } int find ( int x ) { if ( p [ x ] != x ) p [ x ] = find ( p [ x ]); return p [ x ]; } }; class Solution { public: vector < int > findRedundantDirectedConnection ( vector < vector < int >>& edges ) { int n = edges . size (); vector < int > p ( n + 1 ); for ( int i = 0 ; i <= n ; ++ i ) p [ i ] = i ; UnionFind uf ( n + 1 ); int conflict = - 1 , cycle = - 1 ; for ( int i = 0 ; i < n ; ++ i ) { int u = edges [ i ][ 0 ], v = edges [ i ][ 1 ]; if ( p [ v ] != v ) conflict = i ; else { p [ v ] = u ; if ( ! uf . unite ( u , v )) cycle = i ; } } if ( conflict == - 1 ) return edges [ cycle ]; int v = edges [ conflict ][ 1 ]; if ( cycle != - 1 ) return { p [ v ], v }; return edges [ conflict ]; } };
```

### Python

```python
class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . n = n def union ( self , a , b ): if self . find ( a ) == self . find ( b ): return False self . p [ self . find ( a )] = self . find ( b ) self . n -= 1 return True def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] class Solution : def findRedundantDirectedConnection ( self , edges : List [ List [ int ]]) -> List [ int ]: n = len ( edges ) p = list ( range ( n + 1 )) uf = UnionFind ( n + 1 ) conflict = cycle = None for i , ( u , v ) in enumerate ( edges ): if p [ v ] != v : conflict = i else : p [ v ] = u if not uf . union ( u , v ): cycle = i if conflict is None : return edges [ cycle ] v = edges [ conflict ][ 1 ] if cycle is not None : return [ p [ v ], v ] return edges [ conflict ]
```