## Redundant Connection

• Time:O(n\log n)
• Space:O(n)

## C++

``````class UF {
public:
UF(int n) : id(n) {
iota(begin(id), end(id), 0);
}

bool union_(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return false;
id[i] = j;
return true;
}

private:
vector<int> id;

int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
};

class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
UF uf(edges.size() + 1);

for (const auto& e : edges)
if (!uf.union_(e[0], e[1]))
return e;

throw;
}
};
``````

## JAVA

``````class UF {
public UF(int n) {
id = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}

public boolean union(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return false;
id[i] = j;
return true;
}

private int[] id;

private int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
}

class Solution {
public int[] findRedundantConnection(int[][] edges) {
UF uf = new UF(edges.length + 1);

for (int[] e : edges)
if (!uf.union(e[0], e[1]))
return edge;

throw new IllegalArgumentException();
}
}
``````

## Python

``````class UF:
def __init__(self, n: int):
self.id = [i for i in range(n + 1)]

def union(self, u: int, v: int) -> bool:
i = self.find(u)
j = self.find(v)
if i == j:
return False
self.id[i] = j
return True

def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]

class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
uf = UF(len(edges))

for edge in edges:
if not uf.union(edge[0], edge[1]):
return edge
``````