thrownewError('key has to be a function or else left undefined')
}
letcnt,length
// init Union Find with number of distinct groups. Each group will be referred to as index of the array of size 'size' starting at 0.
// Provide an optional key function that maps these indices. I.e., for the groups starting with 1 provide function(a){return a-1;}. The default value is function(a){return a;}.
key=
key||
function(a){
returna
}
cnt=length=n
constid=newArray(n)
constsz=newArray(n)
for(leti=0;i<n;i++){
id[i]=i
sz[i]=1
}
// Returns the number of elements of uf object.
this.size=function(){
returnlength
}
// Returns the number of distinct groups left inside the object.
this.count=function(){
returncnt
}
// Return the root (value) of the group in which p is.
this.find=function(p){
p=key(p)
while(p!==id[p]){
id[p]=id[id[p]]
p=id[p]
}
returnp
}
// Returns true if p and p are both in same group, false otherwise.
this.connected=function(p,q){
p=key(p)
q=key(q)
ensureIndexWithinBounds(p,q)
returnthis.find(p)===this.find(q)
}
// Combine elements in groups p and q into a single group. In other words connect the two groups.
this.union=function(p,q){
p=key(p)
q=key(q)
ensureIndexWithinBounds(p,q)
consti=this.find(p)
constj=this.find(q)
if(i===j)return
if(sz[i]<sz[j]){
id[i]=j
sz[j]+=sz[i]
}else{
id[j]=i
sz[i]+=sz[j]
}
cnt--
}
functionensureIndexWithinBounds(args){
for(leti=arguments.length-1;i>=0;i--){
constp=arguments[i]
if(p>=length)
thrownewError(
'Index out of bounds. The maximum index can be length-1'