Union find algorithm: Leetcode 305 Island count II

Here is the blog I like to learn from.

Union find - disjoint set

algorithms to review:

1. Friend Circles
2. Graph Valid Tree
3. Redundant Connection II

这种群组类问题，很适合使用联合查找 Union Find 来做，又叫并查集 Disjoint Set，LeetCode 中使用这种解法的题目还不少呢，比如 Friend Circles，Graph Valid Tree，Redundant Connection II 等等。

一般来说，UF 算法的思路是每个个体先初始化为不同的群组，然后遍历有关联的两个个体，如果发现其 getRoot 函数的返回值不同，则手动将二者加入一个群组，然后总群组数自减1。

这里就要分别说一下 root 数组，和 getRoot 函数。两个同群组的个体，通过 getRoot 函数一定会返回相同的值，但是其在 root 数组中的值不一定相同，可以类比成 getRoot 函数返回的是祖先，如果两个人的祖先相同，那么其是属于一个家族的（这里不是指人类共同的祖先哈）。

root 可以用数组或者 HashMap 来表示，如果个体是数字的话，那么数组就 OK，如果个体是字符串的话，可能就需要用 HashMap 了。

root 数组的初始化可以有两种，可以均初始化为 -1，或者都初始化为不同的数字，博主一般喜欢初始化为不同的数字。getRoot 函数的写法也可用递归或者迭代的方式，可参见博主之前的帖子 Redundant Connection II 中的讨论部分

Actionable Items

I also practice more than five implementations of union find algorithms. 

Here is the link.