Union find algorithm - Julia likes to set up a C# code for her own use, later add some test cases to help her understand the algorithm one step a time

unionFind_JuliaLibrary.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    /// <summary>
    /// May 10, 2017
    /// Read the union find algorithm lecture note, and add some test cases to help understand the algorithm 
    /// https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/UnionFind.pdf
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {           
            //RunUnionFindTestCase();
        }       
        
        public static void RunUnionFindTestCase()
        {
            var unionFind = new UnionFind();
            var edges = new int[4][];
            edges[0] = new int[] { 0, 0 };
            edges[1] = new int[] { 1, 0 };
            edges[2] = new int[] { 2, 0 };
            edges[3] = new int[] { 2, 0 };

            int count = 0;
            int index = 1;
            foreach (var edge in edges)
            {
                var left = index;
                var right = edge[0];
                var burnout = edge[1];

                if (burnout == 1)
                {
                    continue;
                }

                if (unionFind.IsSameGroup(left, right))
                {
                    count++;
                    continue;
                }

                unionFind.Unite(left, right);

                index++;
            }
            
            var groups = unionFind.GetGroups().Where(v => v != 0).Select(v => v + 1).ToList();

            groups.Sort();
            var result = groups.Sum();
        }
    }

    /// <summary>
    /// 
    /// </summary>
    public class UnionFind
    {
        private class Node
        {
            public Node Parent { get; set; }  // parent -> root node of disjoint set
            public int  Rank { get; set; }
            public int  Id { get; set; }

            public HashSet<Node> Children;

            public Node(int id)
            {
                Id = id; 
                Children = new HashSet<Node>();
            }
        }

        private Dictionary<object, Node> dictionary = new Dictionary<object, Node>();

        /// <summary>
        /// 
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        private Node Root(object data)
        {
            if (!dictionary.ContainsKey(data))
            {
                var node = new Node((int)data);
                dictionary.Add(data, node);
                return node;
            }
            else
            {
                var node = dictionary[data];
                return FindRootSetParent(node);
            }
        }

        /// <summary>
        /// find the root node, and also set node's parent node to root node
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        private Node FindRootSetParent(Node node)
        {
            if (node.Parent == null)
            {
                return node;
            }

            return node.Parent = FindRootSetParent(node.Parent);
        }

        /// <summary>
        /// 1. Connect two disjoint sets, for two input arguments, 
        /// find those two root nodes of disjoint set, and then merge them
        /// Design:
        /// If two nodes have same rank, put the parent node as x argument 
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        public void Unite(IComparable x, IComparable y)
        {
            var xRoot = Root(x);
            var yRoot = Root(y);

            if (xRoot == yRoot)
            {
                return;
            }

            if (xRoot.Rank < yRoot.Rank)
            {
                ChangeParent(yRoot, xRoot);
            }
            else
            {
                ChangeParent(xRoot, yRoot);

                if (xRoot.Rank == yRoot.Rank)
                {
                    xRoot.Rank++;
                }
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="parent"></param>
        /// <param name="childRoot"></param>
        void ChangeParent(Node parent, Node childRoot)
        {
            if (childRoot.Parent != null)
            {
                childRoot.Parent.Children.Remove(childRoot);
            }

            childRoot.Parent = parent;
            childRoot.Parent.Children.Add(childRoot);

            foreach (var child in childRoot.Children.ToList())
            {
                ChangeParent(parent, child);
            }
        }

        /// <summary>
        /// IsSameGroup
        /// Also it sets two nodes in the dictionary 
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        public bool IsSameGroup(IComparable x, IComparable y)
        {
            return Root(x) == Root(y);
        }

        /// <summary>
        /// code review: May 6 2017
        /// </summary>
        /// <returns></returns>
        public List<long> GetGroups()
        {
            var groups = new List<long>();

            foreach (var group in dictionary.Values.Where(d => d.Parent == null))
            {
                groups.Add(group.Children.Count());
            }

            return groups;
        }              
    }
}