UNION FIND DATASTRUCTURE

UNION FIND DATASTRUCTURE

namespace UnionFindDS
{
    class UnionFind
    {
        Dictionary<char, char> PARENT = null;
        Dictionary<char, int> RANK = null;

        public UnionFind()
        {
            PARENT = new Dictionary<char, char>();
            RANK = new Dictionary<char, int>();
        }

        public void AddNewDisjointSet(char c)
        {
            PARENT[c] = c;
            RANK[c] = 0;
        }

        public char Find(char c)
        {
            char root = FindRoot(c);
            PARENT[c] = root;
            return root;
        }

        private char FindRoot(char c)
        {
            if (PARENT[c] != c)
            {
                return Find(PARENT[c]);
            }
            else return c;
        }

        public void Union(char set1, char set2)
        {
            if(set1 == set2) return;
            if(!PARENT.ContainsKey(set1) || !PARENT.ContainsKey(set2))
            {
                throw new InvalidOperationException("One or both of the 2 supplied sets are not present");
            }

            char set1Parent = Find(set1);
            char set2Parent = Find(set2);

            if(set1Parent == set2Parent) return;

            if (RANK[set1Parent] > RANK[set2Parent])
            {
                PARENT[set2Parent] = set1Parent;
            }
            else if (RANK[set2Parent] > RANK[set1Parent])
            {
                PARENT[set1Parent] = set2Parent;
            }
            else
            {
                PARENT[set1Parent] = set2Parent;
                RANK[set2Parent]++;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            UnionFind UF = new UnionFind();
            UF.AddNewDisjointSet('a');
            UF.AddNewDisjointSet('b');
            UF.AddNewDisjointSet('c');
            UF.AddNewDisjointSet('d');
            UF.AddNewDisjointSet('e');
            UF.AddNewDisjointSet('f');
            UF.AddNewDisjointSet('g');

            UF.Union('a','b');
            UF.Union('c','d');
            UF.Union('e','f');
            UF.Union('b','c');
            UF.Union('a','f');
            UF.Union('a', 'g');
        }
    }
}