Union-Find Algorithm
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(); | |
| } | |
| } |
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.