-`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) == true` method is used to determine whether two nodes are in the same tree.

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

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

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

1. As soon as`same_root(node1, node2) == true` (a cycle will be formed), return`[node1, node2]`.

1. As soon as`is_same_root(node1, node2) == true` (a cycle will be formed), return`[node1, node2]`.

* Time:`O(n)`.

classSolution:

def__init__(self):

self.parent=None

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

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

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

for x, yin edges:

ifself.same_root(x, y):

ifself.is_same_root(x, y):

return [x, y]

self.unite(x, y)

root_x=self.find_root(x)

root_y=self.find_root(y)

self.parent[root_y]= root_x# Error-prone point

self.parents[root_y]= root_x# Error-prone point 1

deffind_root(self,x):

if x==self.parent[x]:

parent=self.parents[x]

if x== parent:

return x

self.parent[x]=self.find_root(self.parent[x])

root=self.find_root(parent)# Error-prone point 2

returnself.parent[x]

self.parents[x]= root# Error-prone point 3

return root

defsame_root(self,x,y):

defis_same_root(self,x,y):

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

classSolution {

privateint[]parent;

privateint[]parents;

publicint[]findRedundantConnection(int[][]edges) {

parent=newint[edges.length+1];

parents=newint[edges.length+1];

for (var i=0; i<parent.length; i++) {

parent[i]= i;

for (var i=0; i<parents.length; i++) {

parents[i]= i;

}

for (var edge: edges) {

if (sameRoot(edge[0], edge[1])) {

if (isSameRoot(edge[0], edge[1])) {

return edge;

}

int rootX= findRoot(x);

int rootY= findRoot(y);

parent[rootY]= rootX;// Error-prone point 1

parents[rootY]= rootX;// Error-prone point 1

}

privateintfindRoot(intx) {

if (x== parent[x]) {

var parent= parents[x];

if (x== parent) {

return x;

}

parent[x]= findRoot(parent[x]);// Error-prone point 2

var root= findRoot(parent);// Error-prone point 2

return parent[x];

parents[x]= root;// Error-prone point 3

return root;

}

privatebooleansameRoot(intx,inty) {

privatebooleanisSameRoot(intx,inty) {

return findRoot(x)== findRoot(y);

}

}

public:

vector<int> findRedundantConnection(vector<vector<int>>& edges) {

for (auto i = 0; i <= edges.size(); i++) {

parent.push_back(i);

parents.push_back(i);

}

private:

vector<int>parent;

vector<int>parents;

};

{

int[]parent;

int[]parents;

publicint[]FindRedundantConnection(int[][]edges)

{

parent=newint[edges.Length+1];

parents=newint[edges.Length+1];

for (inti=0;i<parent.Length;i++)

parent[i]=i;

for (inti=0;i<parents.Length;i++)

parents[i]=i;

foreach (int[]edgeinedges)

{

if (sameRoot(edge[0],edge[1]))

if (isSameRoot(edge[0],edge[1]))

{

returnedge;

}

introotX=findRoot(x);

introotY=findRoot(y);

parent[rootY]=rootX;// Error-prone point 1

parents[rootY]=rootX;// Error-prone point 1

}

intfindRoot(intx)

{

if (x==parent[x])

intparent=parents[x];

if (x==parent)

returnx;

parent[x]=findRoot(parent[x]);// Error-prone point 2

introot=findRoot(parent);// Error-prone point 2

returnparent[x];

parents[x]=root;// Error-prone point 3

returnroot;

}

boolsameRoot(intx,inty)

boolisSameRoot(intx,inty)

{

returnfindRoot(x)==findRoot(y);

}

varparent []int

varparents []int

funcfindRedundantConnection(edges [][]int) []int {

parent =make([]int,len(edges) +1)

fori:=0; i <len(parent); i++ {

parent[i] = i

parents =make([]int,len(edges) +1)

fori:=0; i <len(parents); i++ {

parents[i] = i

}

for_,edge:=range edges {

ifsameRoot(edge[0], edge[1]) {

ifisSameRoot(edge[0], edge[1]) {

return edge

}

rootX:=findRoot(x)

rootY:=findRoot(y)

parent[rootY] = rootX// Error-prone point 1

parents[rootY] = rootX// Error-prone point 1

}

funcfindRoot(xint)int {

if x == parent[x] {

parent:= parents[x];

if x == parent {

return x

}

parent[x]=findRoot(parent[x])// Error-prone point 2

root:=findRoot(parent)// Error-prone point 2

return parent[x]

parents[x] = root// Error-prone point 3

return root

}

funcsameRoot(x,yint)bool {

funcisSameRoot(x,yint)bool {

returnfindRoot(x) ==findRoot(y)

}

deffind_redundant_connection(edges)

@parent= []

(0..edges.size).each { |i|@parent<< i }

@parents= []

(0..edges.size).each { |i|@parents<< i }

edges.eachdo |edge|

ifsame_root(edge[0], edge[1])

ifis_same_root(edge[0], edge[1])

return edge

root_x= find_root(x)

root_y= find_root(y)

@parent[root_y]= root_x# Error-prone point 1

@parents[root_y]= root_x# Error-prone point 1

deffind_root(x)

if x==@parent[x]

parent=@parents[x]

if x== parent

return x

@parent[x]= find_root(@parent[x])# Error-prone point 2

root= find_root(parent)# Error-prone point 2

@parents[x]= root# Error-prone point 3

defsame_root(x,y)

defis_same_root(x,y)

find_root(x)== find_root(y)