UnionFind.cs

    public sealed class UnionFind<T>
    {
        private sealed class Link<TLink>
        {
            public TLink parent;
            public int rank = 0;

            public Link(TLink parent)
            {
                this.parent = parent;
            }
        }

        private readonly Dictionary<T, Link<T>> elements
            = new Dictionary<T, Link<T>>();

        /// <summary>
        ///  Creates a new UnionFind structure that is initially empty.
        /// </summary>
        public UnionFind()
        {
        }

        /// <summary>
        ///  Creates a new UnionFind structure that initially contains all of the
        ///  elements from the specified container. Duplicate elements will appear
        ///  with multiplicity one.
        /// </summary>
        /// <param name="elems">
        ///  The elements to store in the UnionFind structure
        /// </param>
        public UnionFind(IEnumerable<T> elems)
        {
            foreach (T elem in elems)
                Add(elem);
        }

        /// <summary>
        ///  Inserts a new element into the UnionFind structure that initially is in
        ///  its own partition. If the element already exists, this function returns
        ///  false. Otherwise, it returns true.
        /// </summary>
        /// <param name="element">
        ///  The element to insert.
        /// </param>
        /// <returns>
        ///  Whether the element was successfully inserted.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">
        ///  If element is null.
        /// </exception>
        public bool Add(T element)
        {
            if (element == null)
                throw new ArgumentNullException("element");

            if (elements.ContainsKey(element))
                return false;

            elements.Add(element, new Link<T>(element));
            return true;
        }

        /// <summary>
        ///  Given an element, returns the representative element of the set
        ///  containing that element. If the element is not contained in the
        ///  structure, this method throws a KeyNotFoundException.
        /// </summary>
        /// <param name="element">
        ///  The element to look up.
        /// </param>
        /// <returns>
        ///  The representative of the set containing the element.
        /// </returns>
        /// <exception cref="System.Collections.Generic.KeyNotFoundException">
        ///  If the element does not exist.
        /// </exception>
        public T Find(T element)
        {
            if (!elements.ContainsKey(element))
                throw new KeyNotFoundException(element + " is not an element.");

            return RecursiveFind(element);
        }

        /// <summary>
        ///  Given an element which is known to be in the structure, searches for its
        ///  representative element and returns it, applying path compression at each
        ///  step.
        /// </summary>
        /// <param name="elem">
        ///  The element to look up.
        /// </param>
        /// <returns>
        ///  The representative of the set containing it.
        /// </returns>
        private T RecursiveFind(T elem)
        {
            Link<T> info = elements[elem];

            if (info.parent.Equals(elem))
                return elem;

            info.parent = RecursiveFind(info.parent);
            return info.parent;
        }

        /// <summary>
        ///  Given two elements, unions together the sets containing those elements.
        ///  If either element is not contained in the set, throws a
        ///  KeyNotFoundException.
        /// </summary>
        /// <param name="one">
        ///  The first element to link.
        /// </param>
        /// <param name="two">
        ///  The second element to link.
        /// </param>
        /// <exception cref="System.Collections.Generic.KeyNotFoundException">
        ///  If either element does not exist.
        /// </exception>
        public void Union(T one, T two)
        {
            Link<T> oneLink = elements[Find(one)];
            Link<T> twoLink = elements[Find(two)];

            if (oneLink == twoLink)
                return;

            if (oneLink.rank > twoLink.rank)
            {
                twoLink.parent = oneLink.parent;
            }
            else if (oneLink.rank < twoLink.rank)
            {
                oneLink.parent = twoLink.parent;
            }
            else
            {
                twoLink.parent = oneLink.parent;
                oneLink.rank++;
            }
        }
    }