# Redundant Connection
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/redundant-connection)
Canonical: https://scaleengineer.com/dsa/problems/redundant-connection
**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
**Companies:** [InMobi](https://scaleengineer.com/companies/inmobi), [Box](https://scaleengineer.com/companies/box)
---
## Problem
In this problem, a tree is an **undirected graph** that is connected and has no cycles.

You are given a graph that started as a tree with `n` nodes labeled from `1` to `n`, with one additional edge added. The added edge has two **different** vertices chosen from `1` to `n`, and was not an edge that already existed. The graph is represented as an array `edges` of length `n` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the graph.

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

**Example 1:**

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

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

**Example 2:**

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

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

**Constraints:**

* `n == edges.length`
* `3 <= n <= 1000`
* `edges[i].length == 2`
* `1 <= ai < bi <= edges.length`
* `ai != bi`
* There are no repeated edges.
* The given graph is connected.

# Approaches
## Graph Traversal (DFS)
This approach involves building the graph edge by edge and checking for cycles using a graph traversal algorithm like Depth-First Search (DFS). We iterate through the given edges in order. For each edge `(u, v)`, we check if there is already a path between nodes `u` and `v` in the graph constructed from the previous edges. If a path exists, adding the current edge `(u, v)` would create a cycle, making it a redundant edge. Since we need to find the redundant edge that appears last in the input, we continue this process for all edges, overwriting our answer each time we find a redundant one. The final stored edge will be the correct answer.
**Time:** O(N^2), where N is the number of nodes (which is equal to the number of edges). For each of the N edges, we may perform a DFS traversal on the graph built so far. The traversal takes O(V + E) time, where V and E are the current number of vertices and edges, both of which are at most O(N). This results in a total time complexity of N * O(N) = O(N^2). · **Space:** O(N), where N is the number of nodes. The space is used for the adjacency list, which can store up to 2*(N-1) entries, and for the `visited` set used in the DFS, which can store up to N nodes.
**Pros:** The logic is intuitive and directly follows the definition of a cycle.; It's relatively easy to implement using standard graph traversal techniques.
**Cons:** The O(N^2) time complexity is less efficient than the Union-Find approach and may be too slow for very large graphs.; It involves repeated traversals over parts of the graph, which is computationally expensive.
### Explanation
We use an adjacency list to represent the graph. We process the edges from the input array one by one. For each edge `[u, v]`, we first perform a check to see if `u` and `v` are already in the same connected component. This check is done by starting a DFS from node `u` and seeing if we can reach node `v`. A `visited` set is crucial during the DFS to keep track of visited nodes and prevent getting stuck in infinite loops if the graph already contains cycles (which is the case we are trying to detect).

If the DFS from `u` successfully reaches `v`, it confirms that adding the edge `[u, v]` would create a cycle. We then mark this edge as the current redundant edge. If the DFS does not reach `v`, the edge connects two previously disconnected components (or adds a new node to a component), so we add it to our adjacency list representation of the graph.

By iterating through all edges and updating the redundant edge whenever one is found, we ensure that the final result is the one that occurs last in the input list.

```java
import java.util.*;

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        int[] redundantEdge = null;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];

            Set<Integer> visited = new HashSet<>();
            if (hasPath(u, v, adj, visited)) {
                redundantEdge = edge;
            } else {
                adj[u].add(v);
                adj[v].add(u);
            }
        }
        return redundantEdge;
    }

    private boolean hasPath(int source, int destination, List<Integer>[] adj, Set<Integer> visited) {
        if (source == destination) {
            return true;
        }
        visited.add(source);
        for (int neighbor : adj[source]) {
            if (!visited.contains(neighbor)) {
                if (hasPath(neighbor, destination, adj, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. Initialize an empty adjacency list `adj` to represent the graph.
2. Initialize a variable `redundantEdge` to store the result.
3. Determine the number of nodes, `n`, which is `edges.length`.
4. Iterate through each `edge = [u, v]` in the `edges` array.
5. For each edge, check if `u` and `v` are already connected in the graph formed by the edges processed so far. This is done by a graph traversal (like DFS).
6. To perform the check, call a helper function, e.g., `hasPath(u, v, adj, new HashSet<>())`.
7. The `hasPath` function starts a DFS from `u` and tries to reach `v`. It uses a `visited` set to avoid infinite loops.
8. If `hasPath` returns `true`, it means `u` and `v` are already connected. Adding the current edge would form a cycle. Thus, this edge is redundant. We update `redundantEdge = edge`.
9. If `hasPath` returns `false`, the edge does not create a cycle at this point. We add it to the graph by updating the adjacency list: `adj[u].add(v)` and `adj[v].add(u)`.
10. After iterating through all the edges, the final value of `redundantEdge` will be the last redundant edge encountered in the input array. Return `redundantEdge`.

## Union-Find (Disjoint Set Union)
A more efficient and standard solution for this problem is to use a Union-Find (or Disjoint Set Union) data structure. This data structure is specifically designed to manage a partition of a set into disjoint subsets, which maps perfectly to tracking the connected components of a graph. We process each edge from the input array. For an edge `(u, v)`, we use the `find` operation to check if `u` and `v` already belong to the same set (i.e., are already connected). If they are, adding this edge creates a cycle, and thus it is redundant. If they are not in the same set, we use the `union` operation to merge their sets, effectively connecting them. We keep track of the last edge that was found to be redundant, which will be our final answer.
**Time:** O(N * α(N)), where N is the number of edges and α(N) is the Inverse Ackermann function. Due to path compression and union by rank optimizations, the amortized time complexity for `find` and `union` operations is nearly constant. We perform these operations for each of the N edges, leading to the overall near-linear time complexity. · **Space:** O(N), where N is the number of nodes. This space is required for the `parent` and `rank` arrays used by the Union-Find data structure.
**Pros:** Extremely efficient, with a nearly linear time complexity, making it suitable for very large graphs.; It is the canonical approach for solving problems related to dynamic connectivity and cycle detection in an incremental graph.
**Cons:** The Union-Find data structure can be less intuitive to understand and implement for those not familiar with it compared to a simple graph traversal.
### Explanation
The Union-Find data structure is initialized with `N` disjoint sets, one for each node in the graph. We typically use a `parent` array for this, where `parent[i]` points to the parent of node `i` in its set's tree representation. A node is the representative (or root) of its set if it points to itself.

We iterate through the `edges` array. For each edge `[u, v]`, we find the roots of `u` and `v`. If their roots are the same, it implies that a path already exists between them, and they are part of the same connected component. Adding the edge `[u, v]` would close a path and form a cycle. We record this edge as our candidate answer. If the roots are different, the edge connects two separate components. We then perform a `union` operation to merge these two components into one.

To make the `find` and `union` operations highly efficient, we employ two key optimizations: path compression and union by rank (or size). Path compression flattens the structure of the tree during `find` operations by making every node on the find path point directly to the root. Union by rank ensures that when merging two trees, the shorter tree is always attached to the root of the taller tree, which helps in keeping the trees from becoming too deep.

By processing all edges and updating our answer whenever a redundant one is found, the final answer will be the correct one as per the problem statement.

```java
class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);
        int[] result = null;

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            if (uf.find(u) == uf.find(v)) {
                result = edge;
            } else {
                uf.union(u, v);
            }
        }
        return result;
    }
}

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    // Find with path compression
    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        parent[i] = find(parent[i]);
        return parent[i];
    }

    // Union by rank
    public boolean union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            return true;
        }
        return false;
    }
}
```
### Algorithm
1. Create a `UnionFind` class (also known as Disjoint Set Union or DSU) that supports `find` and `union` operations. It should be initialized for `N` nodes, where `N` is the number of edges.
2. The `UnionFind` structure typically uses a `parent` array, where `parent[i]` stores the parent of element `i`. Initially, each node is its own parent (`parent[i] = i`).
3. For optimization, use path compression in the `find` operation and union by rank/size in the `union` operation.
4. Initialize a result variable, `resultEdge`, to `null`.
5. Iterate through each `edge = [u, v]` in the input `edges` array.
6. For each edge, find the representatives (roots) of `u` and `v` using the `find` operation: `rootU = find(u)` and `rootV = find(v)`.
7. If `rootU` is equal to `rootV`, it means `u` and `v` are already in the same connected component. Adding this edge would form a cycle. Therefore, this edge is redundant. Update `resultEdge = edge`.
8. If `rootU` is not equal to `rootV`, the nodes are in different components. Merge their components by calling `union(u, v)`.
9. After iterating through all the edges, `resultEdge` will hold the last redundant edge found. Return `resultEdge`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  int[] findRedundantConnection(int[][] edges) {
    p = new int[1010];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      if (find(a) == find(b)) {
        return e;
      }
      p[find(a)] = find(b);
    }
    return null;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} edges * @return {number[]} */ var findRedundantConnection =
  function (edges) {
    let p = Array.from({ length: 1010 }, (_, i) => i);
    function find(x) {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    }
    for (let [a, b] of edges) {
      if (find(a) == find(b)) {
        return [a, b];
      }
      p[find(a)] = find(b);
    }
    return [];
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  vector<int> findRedundantConnection(vector<vector<int>> &edges) {
    p.resize(1010);
    for (int i = 0; i < p.size(); ++i)
      p[i] = i;
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      if (find(a) == find(b))
        return e;
      p[find(a)] = find(b);
    }
    return {};
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(1010)) for a, b in edges: if find(a) == find(b): return [a, b] p[find(a)] = find(b) return []

```