0261-graph-valid-tree.swift

classDisjointSet{
privatevarranks:[Int]
privatevarroots:[Int]

init(numVertices:Int){
 ranks =[Int](repeating:0, count: numVertices)
 roots =[Int](repeating:0, count: numVertices)

foriin0..<numVertices {
roots[i]= i
ranks[i]=1
}
}

publicfunc union(v1 x:Int, v2 y:Int){
letrootX=find(of: x)
letrootY=find(of: y)

guard rootX != rootY else{return}

letrankX=ranks[rootX]
letrankY=ranks[rootY]

if rankX > rankY { // go into X
roots[rootY]= rootX
}elseif rankY > rankX { // go into Y
roots[rootX]= rootY
}else{ // go into X by default
roots[rootY]= rootX
ranks[rootX]+=1
}
}

privatefunc find(of x:Int)->Int{
ifroots[x]== x {return x }
roots[x]=find(of:roots[x])
returnroots[x]
}

publicfunc areConnected(v1:Int, v2:Int)->Bool{
find(of: v1)==find(of: v2)
}

publicfunc areDisjoint(v1:Int, v2:Int)->Bool{
 !areConnected(v1: v1, v2: v2)
}
}

classSolution{
func validTree(_ n:Int, _ edges:[[Int]])->Bool{
 // Check if n-1 edges
letnumEdges= edges.count
guard numEdges ==(n -1)else{returnfalse}

 // Check if connected => Can use DisjointSet/UnionFind
letds=DisjointSet(numVertices: n)
foredgein edges {
letv1=edge[0]; letv2=edge[1]
guard ds.areDisjoint(v1: v1, v2: v2)else{
returnfalse
}
 ds.union(v1: v1, v2: v2)
}

returntrue;
}
}