-`UnionFind` algorithm typically has three methods:

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

- The`find_root(node)` method can be 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. Initially, each node is in its own group.

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

1. Return`same_root(source, destination)`.

1. Return`is_same_root(source, destination)`.

* Time:`O(n)`.

classSolution:

def__init__(self):

self.parent=None

defvalidPath(self,n:int,edges: List[List[int]],source:int,destination:int) ->bool:

self.parent=list(range(n))

self.parents=list(range(n))

for x, yin edges:

self.unite(x, y)

returnself.same_root(source, destination)

returnself.is_same_root(source, destination)

defunite(self,x,y):

root_x=self.find_root(x)

root_y=self.find_root(y)

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

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])# Error-prone point 2

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

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

defsame_root(self,x,y):

defis_same_root(self,x,y):

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

classSolution {

privateint[]parent;

privateint[]parents;

publicbooleanvalidPath(intn,int[][]edges,intsource,intdestination) {

parent=newint[n];

parents=newint[n];

for (var i=0; i< n; i++) {

parent[i]= i;

parents[i]= i;

}

for (var edge: edges) {

unite(edge[0], edge[1]);

}

returnsameRoot(source, destination);

returnisSameRoot(source, destination);

}

privatevoidunite(intx,inty) {

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

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

returnparent[x];

returnroot;

}

privatebooleansameRoot(intx,inty) {

privatebooleanisSameRoot(intx,inty) {

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

}

}

public:

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {

for (auto i = 0; i < n; i++) {

parent.push_back(i);

parents.push_back(i);

}

returnsameRoot(source, destination);

returnisSameRoot(source, destination);

}

vector<int>parent;

vector<int>parents;

voidunite(int x, int y) {

int root_x = findRoot(x);

int root_y = findRoot(y);

};

{

int[]parent;

int[]parents;

publicboolValidPath(intn,int[][]edges,intsource,intdestination)

{

parent=newint[n];

parents=newint[n];

for (inti=0;i<n;i++)

parent[i]=i;

parents[i]=i;

foreach (int[]edgeinedges)

{

unite(edge[0],edge[1]);

}

returnsameRoot(source,destination);

returnisSameRoot(source,destination);

}

voidunite(intx,inty)

{

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

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

returnparent[x];

returnroot;

}

boolsameRoot(intx,inty)

boolisSameRoot(intx,inty)

{

returnfindRoot(x)==findRoot(y);

}

varparent []int

varparents []int

funcvalidPath(nint,edges [][]int,sourceint,destinationint)bool {

parent =make([]int, n)

parents =make([]int, n)

fori:=0; i < n; i++ {

parent[i] = i

parents[i] = i

}

for_,edge:=range edges {

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

}

returnsameRoot(source, destination)

returnisSameRoot(source, destination)

}

funcunite(x,yint) {

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

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

}

funcsameRoot(x,yint)bool {

funcisSameRoot(x,yint)bool {

returnfindRoot(x) ==findRoot(y)

}

defvalid_path(n,edges,source,destination)

@parent= []

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

@parents= (0...n).to_a

edges.eachdo |edge|

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

same_root(source, destination)

is_same_root(source, destination)

defunite(x,y)

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)