【题目描述】
Given a boolean 2D matrix, 0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.
Find the number of islands.
给一个01矩阵，求不同的岛屿的个数。
0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
【题目链接】
www.lintcode.com/en/problem/number-of-islands/
【题目解析】
Union Find 利用Union Find的find和union操作，对岛屿进行合并计数。因为UnionFind结构一般来说是一维的
| 1 | 2 | 3 | 4 |
-----------------
| 2 | 2 | 2 | 4 |
表达了如下的连通结构
1 - 2 4
| /
3
因此可以转换二维矩阵坐标为一维数字，M N 的矩阵中`(i,j) -> i N + j`。
建立UnionFind的parent[] (或者 parent hashmap)，初始化各个parent[i * N + j] = i * N + j，如果grid[i][j] == true，则岛屿计数count++
之后再对矩阵遍历一次，当遇到岛屿时，则要检查上下左右四个方向的邻近点，如果也是岛屿则合并，并且count--；
Union Find结构可以用Path Compression和Weighted Union进行优化。
【参考答案】
