##### Welcome to Subscribe On Youtube
• /**

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., 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 resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

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 given 2D-array. The answer edge [u, v] should be in the same format, with u < v.

Example 1:
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
1
/ \
2 - 3
Example 2:
Input: [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1,4]
Explanation: The given undirected graph will be like this:
5 - 1 - 2
|   |
4 - 3
Note:
The size of the input 2D-array will be between 3 and 1000.
Every integer represented in the 2D-array will be between 1 and N, where N is the size of the input array.

*/

public class Redundant_Connection {

}

############

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];
}
}

• // OJ: https://leetcode.com/problems/redundant-connection/
// Time: O(N)
// Space: O(N)
class UnionFind {
private:
vector<int> id, rank;
int cnt;
public:
UnionFind(int cnt) : cnt(cnt) {
id = vector<int>(cnt);
rank = vector<int>(cnt, 0);
for (int i = 0; i < cnt; ++i) id[i] = i;
}
int find(int p) {
if (id[p] == p) return p;
return id[p] = find(id[p]);
}
int getCount() { return cnt; }
bool connected(int p, int q) { return find(p) == find(q); }
void connect(int p, int q) {
int i = find(p), j = find(q);
if (i == j) return;
if (rank[i] < rank[j]) id[i] = j;
else {
id[j] = i;
if (rank[i] == rank[j]) rank[j]++;
}
--cnt;
}
};

class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
UnionFind uf(edges.size());
for (auto e : edges) {
if (uf.connected(e[0] - 1, e[1] - 1)) return e;
uf.connect(e[0] - 1, e[1] - 1);
}
}
};

• 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 []

############

class Solution:
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
tree = [-1] * (len(edges) + 1)
for edge in edges:
a = self.findRoot(edge[0], tree)
b = self.findRoot(edge[1], tree)
if a != b:
tree[a] = b
else:
return edge

def findRoot(self, x, tree):
if tree[x] == -1: return x
else:
root = self.findRoot(tree[x], tree)
tree[x] = root
return root

• func findRedundantConnection(edges [][]int) []int {
p := make([]int, 1010)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range edges {
a, b := e[0], e[1]
if find(a) == find(b) {
return e
}
p[find(a)] = find(b)
}
return []int{}
}

• /**
* @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 [];
};


• class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] redundantConnection = new int[2];
Map<Integer, Integer> nodeGroupMap = new HashMap<Integer, Integer>();
Map<Integer, Set<Integer>> groupNodesMap = new HashMap<Integer, Set<Integer>>();
int nodesCount = edges.length;
for (int i = 1; i <= nodesCount; i++) {
nodeGroupMap.put(i, i);
Set<Integer> set = new HashSet<Integer>();
groupNodesMap.put(i, set);
}
for (int i = 0; i < nodesCount; i++) {
int[] edge = edges[i];
int node1 = edge[0], node2 = edge[1];
int group1 = nodeGroupMap.getOrDefault(node1, node1);
int group2 = nodeGroupMap.getOrDefault(node2, node2);
if (group1 == group2) {
redundantConnection[0] = node1;
redundantConnection[1] = node2;
break;
} else {
Set<Integer> set1 = groupNodesMap.getOrDefault(group1, new HashSet<Integer>());
Set<Integer> set2 = groupNodesMap.getOrDefault(group2, new HashSet<Integer>());
if (group1 < group2) {
for (int node : set2)
nodeGroupMap.put(node, group1);
groupNodesMap.put(group1, set1);
} else {
for (int node : set1)
nodeGroupMap.put(node, group2);
groupNodesMap.put(group2, set2);
}
}
}
return redundantConnection;
}
}

############

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];
}
}

• // OJ: https://leetcode.com/problems/redundant-connection/
// Time: O(N)
// Space: O(N)
class UnionFind {
private:
vector<int> id, rank;
int cnt;
public:
UnionFind(int cnt) : cnt(cnt) {
id = vector<int>(cnt);
rank = vector<int>(cnt, 0);
for (int i = 0; i < cnt; ++i) id[i] = i;
}
int find(int p) {
if (id[p] == p) return p;
return id[p] = find(id[p]);
}
int getCount() { return cnt; }
bool connected(int p, int q) { return find(p) == find(q); }
void connect(int p, int q) {
int i = find(p), j = find(q);
if (i == j) return;
if (rank[i] < rank[j]) id[i] = j;
else {
id[j] = i;
if (rank[i] == rank[j]) rank[j]++;
}
--cnt;
}
};

class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
UnionFind uf(edges.size());
for (auto e : edges) {
if (uf.connected(e[0] - 1, e[1] - 1)) return e;
uf.connect(e[0] - 1, e[1] - 1);
}
}
};

• 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 []

############

class Solution:
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
tree = [-1] * (len(edges) + 1)
for edge in edges:
a = self.findRoot(edge[0], tree)
b = self.findRoot(edge[1], tree)
if a != b:
tree[a] = b
else:
return edge

def findRoot(self, x, tree):
if tree[x] == -1: return x
else:
root = self.findRoot(tree[x], tree)
tree[x] = root
return root

• func findRedundantConnection(edges [][]int) []int {
p := make([]int, 1010)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range edges {
a, b := e[0], e[1]
if find(a) == find(b) {
return e
}
p[find(a)] = find(b)
}
return []int{}
}

• /**
* @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 [];
};