# Graphs: Disjoint Sets for Number of Provinces problem complexity O(n`3)

Fri Jan 14 2022 17:49:57 GMT+0000 (UTC)

Saved by @NeTcpMoeIp #c#

public class DisjointSet{
public int[] Array;

public DisjointSet(int[] array){
Array = array;
}

public int FindParent(int index){
if(Array[index] == -1){
return index;
}

return FindParent(Array[index]);
}

public void Union(int el1, int el2){
var el1Parent = FindParent(el1);
var el2Parent = FindParent(el2);
if(el1Parent != el2Parent){
Array[el1Parent] = el2Parent;
}
}
}

public class DisjointSetOptimization{
public int[] Array;
private int[] _rank;

public DisjointSetOptimization(int[] array){
Array = array;
_rank = Enumerable.Repeat(1, array.Length).ToArray();
}

public int FindParent(int index){
if(Array[index] == -1){
return index;
}

return Array[index] = FindParent(Array[index]);
}

public void Union(int el1, int el2){
var el1Parent = FindParent(el1);
var el2Parent = FindParent(el2);
if(el1Parent == el2Parent){
return;
}

if(_rank[el1Parent] > _rank[el2Parent]){
Array[el2Parent] = el1Parent;
} else if(_rank[el1Parent] < _rank[el2Parent]){
Array[el1Parent] = el2Parent;
} else {
Array[el2Parent] = el1Parent;
_rank[el1Parent]++;
}
}
}
content_copyCOPY

Disjoint Set examples on c# and optimized

https://leetcode.com/problems/number-of-provinces/submissions/