Union-Find Algorithm

Broken Post? → Let me know

Featured Image - "Union St. Street Sign in Bodie" by m01229, used under CC BY-NC 2.0 (Medium sized image)

There is a really cool course on Coursera regarding Union-Find. The course was quite refreshing because I was never exposed to this simple concept before.

I just wanted to share the link for those learning graph theory as I am.

Now comes the boring stuff (how I found out about it and what I did with it).

I ran into a problem solving a question, Maximal Tourism on HackerRank. The problem is about getting most connected node counts in a graph given sets of connected nodes per line.

It seemed like a very simple problem but I had trouble due to timeouts. I wanted to get some tips on how to solve the problem so I decided to check Discussion forum (I try to solve myself for hours or days before resorting to this usually).

Mikhail(@mikesmnx) posted a link to a Coursera course for those having a problem solving the problem. I was hesitant at first but decided to watch the video. After the first video in the course, I started digging it. After finishing the course, I screamed, "I know Kung-Fu".

Union-Find made me realize the flaw in my approach that I was just busy finding ways to build graphs. The better way was to caching or keeping track of connected nodes as I am building the graph. Using a tree structure never came into my mind during my attempts to solve it before watching the course.

Here is the C# version of Union-Find converted from Java (using Improved algorithm, which tracks sizes)

      
        internal class QuickUnionUF
      
        {
      
          private readonly int[] _id;
      
          private readonly int[] _size;
      
          public QuickUnionUF(int n)
      
          {
      
            _id = new int[n + 1];
      
            _size = new int[n + 1];
      
            for (int i = 0; i < n; i++)
      
            {
      
              _id[i] = i;
      
              _size[i] = 1;
      
            }
      
          }
      
          private int GetRoot(int i)
      
          {
      
            while (i != _id[i])
      
              i = _id[i];
      
            return i;
      
          }
      
          public bool IsConnected(int p, int q)
      
          {
      
            return GetRoot(p) == GetRoot(q);
      
          }
      
          public void Union(int p, int q)
      
          {
      
            int i = GetRoot(p);
      
            int j = GetRoot(q);
      
            if (i == j) return;
      
            if (_size[i] < _size[j])
      
            {
      
              _id[i] = j;
      
              _size[j] += _size[i];
      
            }
      
            else
      
            {
      
              _id[j] = i;
      
              _size[i] += _size[j];
      
            }
      
          }
      
          public int GetMaximumConnectedRoute()
      
          {
      
            return _size.Max();
      
          }
      
        }

view raw QuickUnionUF.cs hosted with ❤ by GitHub

I was able to solve the problem with this code without any timeouts. Learning a new algorithm will make your day as well!

The full source for the Maximal Tourism answer is posted on GitHub.

Conclusion

Check out Union-Find and see how you can integrate it into your existing code base.

You can find Union-Find algorithm applications in the last video in the course.

	internal class QuickUnionUF
	{
	private readonly int[] _id;
	private readonly int[] _size;

	public QuickUnionUF(int n)
	{
	_id = new int[n + 1];
	_size = new int[n + 1];
	for (int i = 0; i < n; i++)
	{
	_id[i] = i;
	_size[i] = 1;
	}
	}

	private int GetRoot(int i)
	{
	while (i != _id[i])
	i = _id[i];
	return i;
	}

	public bool IsConnected(int p, int q)
	{
	return GetRoot(p) == GetRoot(q);
	}

	public void Union(int p, int q)
	{
	int i = GetRoot(p);
	int j = GetRoot(q);
	if (i == j) return;
	if (_size[i] < _size[j])
	{
	_id[i] = j;
	_size[j] += _size[i];
	}
	else
	{
	_id[j] = i;
	_size[i] += _size[j];
	}
	}

	public int GetMaximumConnectedRoute()
	{
	return _size.Max();
	}
	}