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

PHOTO EMBED

Fri Jan 14 2022 18:25:00 GMT+0000 (UTC)

Saved by @NeTcpMoeIp #c#

    public class DisjointSetOptimization{
        public int[] Array;
        private int[] _rank;
        public int NotJoinedCount;
        
        public DisjointSetOptimization(int len){
            NotJoinedCount = len;
            Array = Enumerable.Repeat(-1, len).ToArray();
            _rank = Enumerable.Repeat(-1, len).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]++;
            }
            
            NotJoinedCount--;
        }
    }
content_copyCOPY

Graphs: Number of Provinces Version with O(n`2) complexity

https://leetcode.com/explore/learn/card/graph/618/disjoint-set/3845/