Learn quick union algorithm - what is quick? what is union? quick is to connect one group's root to another's group root, union is connecting two trees.

quickUnion_Algorithm.cs

    /// <summary>
    /// understanding the quick union
    /// http://blog.csdn.net/dm_vincent/article/details/7655764
    /// </summary>
    public class QuickUnion
    {
        private int[] id;    // access to component id (site indexed)  
        private int count; // number of components 

        public QuickUnion(int N)
        {
            // Initialize component id array.  
            count = N;
            id = new int[N];
            for (int i = 0; i < N; i++)
            {
                id[i] = i;
            }
        }

        public int GetCount()
        {
            return count;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        /// <summary>
        /// quick find algorithm Find method
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public int Find_QuickFind(int p)
        {
            return id[p];
        }

        /// <summary>
        /// quick union algorithm Find method
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        private int Find(int p)
        {           
            // Look for node p's group root node, 
            // root node can be determined by id[root] = root. 
            while (p != id[p])
            {
                p = id[p];
            }

            return p;
        }  

        /// <summary>
        /// quick find algorithm Union
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        public void Union_quickFind(int p, int q)
        {
            int pID = Find(p);
            int qID = Find(q);

            if (pID == qID)
            {
                return;
            }

            // Find the pID, and make them one group
            for (int i = 0; i < id.Length; i++)
            {
                if (id[i] == pID)
                {
                    id[i] = qID;
                }
            }

            // update count of groups
            count--;
        }

        /// <summary>
        /// quick union algorithm Union method
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        public void Union(int p, int q)
        {
            // Give p and q the same root.  
            int pRoot = Find(p);
            int qRoot = Find(q);

            if (pRoot == qRoot)
            {
                return;
            }

            // 将一颗树(即一个组)变成另外一课树(即一个组)的子树 
            // set one tree to another tree's subtree
            id[pRoot] = qRoot; 
    
            // update count of groups
            count--;
        }  
    } 

March 26, 2019
Good to read the comment about quick and union.