# Redundant Connection LeetCode Solution

Here, We see Redundant Connection LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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:

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

Example 2:

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

## Redundant Connection LeetCode Solution C++

``````class Solution {
public:
vector<int> parent;
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
if(edges.size()==0) return{};
parent.resize(edges.size()+1);
for(int i=1;i<edges.size()+1;i++){
parent[i]=i;
}
for(vector<int> edge : edges){
int f1=find(edge[0]);
int f2=find(edge[1]);
if(f1!=f2)
parent[f1]=f2;
else
return edge;
}
return {};
}
int find(int x){
return parent[x]==x ? x : find(parent[x]);
}
};```Code language: PHP (php)```

## Redundant Connection Solution Java

``````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);
}
}```Code language: PHP (php)```

## Redundant Connection Solution JavaScript

``````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)
};```Code language: JavaScript (javascript)```

## Redundant Connection Solution Python

``````class Solution(object):
def findRedundantConnection(self, edges):
par = [i for i in range(len(edges) + 1)]
def find(x):
if x != par[x]: par[x] = find(par[x])
return par[x]
def union(x, y):
par[find(y)] = find(x)
for a,b in edges:
if find(a) == find(b): return [a,b]
else: union(a,b)``````
Scroll to Top