*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #684 (*Medium*): Redundant Connection

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

In this problem, a tree is an

undirected graphthat 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 twodifferentvertices 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.

####
*Examples:*

*Examples:*

Example 1: Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3] Visual:

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

####
*Constraints:*

*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.

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

In this problem, the redundant edge will be the one that links together an already-linked graph. To determine whether already-seen segments of the graph have been connected, we can use a simple **union-find** (**UF**) implementation to keep track of the different segments.

With **UF**, we must define two functions: **union** and **find**. The **find** function will **recursively** trace a node's lineage back to its ultimate parent and update its value in the parent array (**par**), providing a shortcut for the next link.

The **union** function merges two segments by assigning the ultimate parent of one segment to another.

We can iterate through **edges** and **find** both vertices of the edge to see if they belong to the same segment. If so, we've located our redundant edge and can **return** it. If not, we should merge the two different segments with **union**.

**Time Complexity: O(N)**where**N**is the length of**edges****Space Complexity: O(N)**for**par**and the recursion stack

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var findRedundantConnection = function(edges) {
let par = Array.from({length: edges.length + 1}, (_,i) => i)
const find = x => x === par[x] ? par[x] : par[x] = find(par[x])
const union = (x,y) => par[find(y)] = find(x)
for (let [a,b] of edges)
if (find(a) === find(b)) return [a,b]
else union(a,b)
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
par = [i for i in range(len(edges) + 1)]
def find(x: int) -> int:
if x != par[x]: par[x] = find(par[x])
return par[x]
def union(x: int, y: int) -> None:
par[find(y)] = find(x)
for a,b in edges:
if find(a) == find(b): return [a,b]
else: union(a,b)
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int[] findRedundantConnection(int[][] edges) {
par = new int[edges.length+1];
for (int i = 0; i < par.length; i++)
par[i] = i;
for (int[] e : edges)
if (find(e[0]) == find(e[1])) return e;
else union(e[0],e[1]);
return edges[0];
}
private int[] par;
private int find(int x) {
if (x != par[x]) par[x] = find(par[x]);
return par[x];
}
private void union(int x, int y) {
par[find(y)] = find(x);
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
par.resize(edges.size()+1);
for (int i = 0; i < par.size(); i++)
par[i] = i;
for (auto& e : edges)
if (find(e[0]) == find(e[1])) return e;
else uniun(e[0],e[1]);
return edges[0];
}
private:
vector<int> par;
int find(int x) {
if (x != par[x]) par[x] = find(par[x]);
return par[x];
}
void uniun(int x, int y) {
par[find(y)] = find(x);
}
};
```

## Top comments (3)

we don't have the root so solution is illegal

let/s say we have not

`[[1,2],[2,3],[3,4],[4,1],[1,5]]`

but`[[4,1],[1,2],[2,3],[3,4],[1,5]]`

insteadFrom the problem description:

`edges[i] = [ai, bi]`

...and from the constraints:

`1 <= ai < bi <= edges.length`

Your test case is invalid, as

`[4,1]`

is a case of`ai > bi`

, violating the constraints.If you meant

`[1,4]`

instead, then the code still works. It doesn't rely on a root, but the instructions state:If there are multiple answers, return the answer that occurs last in the input.For the case of

`[[1,2],[2,3],[3,4],[1,4],[1,5]]`

, the code returns the correct answer of`[1,4]`

.For the case of

`[[1,4],[1,2],[2,3],[3,4],[1,5]]`

, the code returns the correct answer of`[3,4]`

.This is observable directly on leetcode's page for this problem.

why you have q[0] in while loop and why not queue.length