## DEV Community is a community of 700,720 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Redundant Connection seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.

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.

#### Description:

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

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.

#### 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:

• `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:

(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:

``````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:

``````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:

``````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) == find(e)) return e;
else union(e,e);
return edges;
}
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:

``````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) == find(e)) return e;
else uniun(e,e);
return edges;
}
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);
}
};
``````