-`UnionFind` algorithm typically has three methods:

- The`unite(node1, node2)` operation is used to merge two trees.

- The`find_root(node)` method is used to return the root of a node.

- The`same_root(node1, node2)` method is used to determine whether two nodes are in the same tree.

- The`is_same_root(node1, node2)` method is used to determine whether two nodes are in the same tree.

1. Iterate`edges` data to look for the`two_conflict_edges` (the two edges caused a vertex with in-degree 2).

1. Initially, each node is in its own group.

1. Iterate`edges` data and`unite(node1, node2)`.

1. If there is no vertex with in-degree 2, as soon as`same_root(node1, node2) == true` (a cycle will be formed), return`[node1, node2]`.

1. If there is no vertex with in-degree 2, as soon as`is_same_root(node1, node2) == true` (a cycle will be formed), return`[node1, node2]`.

1. If there is a vertex with in-degree 2, we need to determine which edge in`two_conflict_edges` should be returned.

See if the graph can form a cycle by not adding the second edge to the graph. If so, return the first edge. Otherwise, return the second edge.

classSolution:

def__init__(self):

self.parent=None

deffindRedundantDirectedConnection(self,edges: List[List[int]]) -> List[int]:

self.parent=list(range(len(edges)+1))

conflict_edges= two_conflict_edges(edges)

self.parents=list(range(len(edges)+1))

ifnot conflict_edges:

two_conflict_edges_=self.two_conflict_edges(edges)

ifnot two_conflict_edges_:

for x, yin edges:

ifself.same_root(x, y):

ifself.is_same_root(x, y):

return [x, y]

self.unite(x, y)

raiseException('No suitable edge was returned')

raiseException('No suitable edge was returned!')

for x, yin edges:

if [x, y]==conflict_edges[1]:

if [x, y]==two_conflict_edges_[1]:

ifself.same_root(x, y):

returnconflict_edges[0]

ifself.is_same_root(x, y):

returntwo_conflict_edges_[0]

self.unite(x, y)

return conflict_edges[1]

defunite(self,x,y):

self.parent[y]= x

return two_conflict_edges_[1]

deffind_root(self,node):

ifself.parent[node]== node:

return node

deftwo_conflict_edges(self,edges):

pointed_node_to_source_node= {}

returnself.find_root(self.parent[node])

defsame_root(self,x,y):

returnself.find_root(x)==self.find_root(y)

for source_node, pointed_nodein edges:

if pointed_nodein pointed_node_to_source_node:

return [

[pointed_node_to_source_node[pointed_node], pointed_node],

[source_node, pointed_node],

]

pointed_node_to_source_node[pointed_node]= source_node

deftwo_conflict_edges(edges):

conflict_edges= []

child_to_parent= {}

return []

for parent, childin edges:

if childin child_to_parent:

conflict_edges.append([child_to_parent[child], child])

conflict_edges.append([parent, child])

defunite(self,x,y):

root_x=self.find_root(x)

root_y=self.find_root(y)

self.parents[root_y]= root_x

deffind_root(self,x):

parent=self.parents[x]

child_to_parent[child]= parent

if x== parent:

return x

root=self.find_root(parent)

return conflict_edges

self.parents[x]= root

return root

defis_same_root(self,x,y):

returnself.find_root(x)==self.find_root(y)

-`UnionFind` algorithm typically has three methods:

- The`unite(node1, node2)` operation is used to merge two trees.

- The`find_root(node)` method is used to return the root of a node.

- The`same_root(node1, node2)` method is used to determine whether two nodes are in the same tree.

- The`is_same_root(node1, node2)` method is used to determine whether two nodes are in the same tree.

1. Iterate`edges` data to look for the`two_conflict_edges` (the two edges caused a vertex with in-degree 2).

1. Initially, each node is in its own group.

1. Iterate`edges` data and`unite(node1, node2)`.

1. If there is no vertex with in-degree 2, as soon as`same_root(node1, node2) == true` (a cycle will be formed), return`[node1, node2]`.

1. If there is no vertex with in-degree 2, as soon as`is_same_root(node1, node2) == true` (a cycle will be formed), return`[node1, node2]`.

1. If there is a vertex with in-degree 2, we need to determine which edge in`two_conflict_edges` should be returned.

See if the graph can form a cycle by not adding the second edge to the graph. If so, return the first edge. Otherwise, return the second edge.

classSolution:

def__init__(self):

self.parent=None

deffindRedundantDirectedConnection(self,edges: List[List[int]]) -> List[int]:

self.parent=list(range(len(edges)+1))

conflict_edges= two_conflict_edges(edges)

self.parents=list(range(len(edges)+1))

ifnot conflict_edges:

two_conflict_edges_=self.two_conflict_edges(edges)

ifnot two_conflict_edges_:

for x, yin edges:

ifself.same_root(x, y):

ifself.is_same_root(x, y):

return [x, y]

self.unite(x, y)

raiseException('No suitable edge was returned')

raiseException('No suitable edge was returned!')

for x, yin edges:

if [x, y]==conflict_edges[1]:

if [x, y]==two_conflict_edges_[1]:

ifself.same_root(x, y):

returnconflict_edges[0]

ifself.is_same_root(x, y):

returntwo_conflict_edges_[0]

self.unite(x, y)

return conflict_edges[1]

defunite(self,x,y):

self.parent[y]= x

return two_conflict_edges_[1]

deffind_root(self,node):

ifself.parent[node]== node:

return node

deftwo_conflict_edges(self,edges):

pointed_node_to_source_node= {}

returnself.find_root(self.parent[node])

defsame_root(self,x,y):

returnself.find_root(x)==self.find_root(y)

for source_node, pointed_nodein edges:

if pointed_nodein pointed_node_to_source_node:

return [

[pointed_node_to_source_node[pointed_node], pointed_node],

[source_node, pointed_node],

]

pointed_node_to_source_node[pointed_node]= source_node

deftwo_conflict_edges(edges):

conflict_edges= []

child_to_parent= {}

return []

for parent, childin edges:

if childin child_to_parent:

conflict_edges.append([child_to_parent[child], child])

conflict_edges.append([parent, child])

defunite(self,x,y):

root_x=self.find_root(x)

root_y=self.find_root(y)

self.parents[root_y]= root_x

deffind_root(self,x):

parent=self.parents[x]

child_to_parent[child]= parent

if x== parent:

return x

root=self.find_root(parent)

return conflict_edges

self.parents[x]= root

return root

defis_same_root(self,x,y):

returnself.find_root(x)==self.find_root(y)