• Time:O(|V|)
• Space:O(|V|)

## 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> findRedundantDirectedConnection(vector<vector<int>>& edges) {
vector<int> ids(edges.size() + 1);
int nodeWithTwoParents = 0;

for (const auto& e : edges) {
const int v = e[1];
if (++ids[v] == 2) {
nodeWithTwoParents = v;
break;
}
}

// if there is no edge with two ids
// we don't have to skip any edge
if (!nodeWithTwoParents)
return findRedundantDirectedConnection(edges, -1);

for (int i = edges.size() - 1; i >= 0; --i)
if (edges[i][1] == nodeWithTwoParents)
// try to delete edges[i]
if (findRedundantDirectedConnection(edges, i).empty())
return edges[i];

throw;
}

vector<int> findRedundantDirectedConnection(const vector<vector<int>>& edges,
int skippedEdgeIndex) {
UF uf(edges.size() + 1);

for (int i = 0; i < edges.size(); ++i) {
if (i == skippedEdgeIndex)
continue;
if (!uf.union_(edges[i][0], edges[i][1]))
return edges[i];
}

return {};
}
};
``````

## 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[] findRedundantDirectedConnection(int[][] edges) {
int[] ids = new int[edges.length + 1];
int nodeWithTwoParents = 0;

for (int[] e : edges) {
final int v = e[1];
if (++ids[v] == 2) {
nodeWithTwoParents = v;
break;
}
}

// if there is no edge with two ids
// we don't have to skip any edge
if (nodeWithTwoParents == 0)
return findRedundantDirectedConnection(edges, -1);

for (int i = edges.length - 1; i >= 0; --i)
if (edges[i][1] == nodeWithTwoParents)
// try to delete edges[i]
if (findRedundantDirectedConnection(edges, i).length == 0)
return edges[i];

throw new IllegalArgumentException();
}

private int[] findRedundantDirectedConnection(int[][] edges, int skippedEdgeIndex) {
UF uf = new UF(edges.length + 1);

for (int i = 0; i < edges.length; ++i) {
if (i == skippedEdgeIndex)
continue;
if (!uf.union(edges[i][0], edges[i][1]))
return edges[i];
}

return new int[] {};
}
}
``````

## 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 findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
ids = [0] * (len(edges) + 1)
nodeWithTwoParents = 0

for u, v in edges:
ids[v] += 1
if ids[v] == 2:
nodeWithTwoParents = v

def findRedundantDirectedConnection(skippedEdgeIndex: int) -> List[int]:
uf = UF(len(edges) + 1)

for i, edge in enumerate(edges):
if i == skippedEdgeIndex:
continue
if not uf.union(edge[0], edge[1]):
return edge

return []

# if there is no edge with two ids
# we don't have to skip any edge
if nodeWithTwoParents == 0:
return findRedundantDirectedConnection(-1)

for i in reversed(range(len(edges))):
_, v = edges[i]
if v == nodeWithTwoParents:
# try to delete edges[i]
if not findRedundantDirectedConnection(i):
return edges[i]
``````