Number of Islands II -- 并查集的应用

今天在Lintcode上刷到Number of Islands II这道题，发现恰好和前两天面经版的一个Youtube面试出现的题的follow up是相同的。在网上简单搜了一下并没有看到关于这道题的详细解法，所以自己写了一个，分享给大家。

原题是这样的：

----------------------

1. Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.
   
2. 
   
3. Example
   
4. 
   
5. Given n = 3, m = 3, array of pair A = [(0,0),(0,1),(2,2),(2,1)].
   
6. 
   
7. return [1,1,2,2].
   
8. 
   
9. Note
   
10. 
    
11. 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
    

复制代码

大意就是在一个由grid组成的海洋上，每次将一个方格从海洋改变成陆地。在每次完成这个操作后，都要得到此时的岛屿数目。
--------------------

这实际上就是要动态维护一个图的Connected Component。这是并查集(Union-find set)的典型应用。所谓并查集，就是满足下列特征的数据结构：

1. 能表示一组不相交的集合，比如{{1, 2, 3}, {4, 5}, {6}, {7}}；
2. 最少支持以下三个操作:
    make-set(v): 加入一个新的集合，其中只有一个元素v。
    find(v): 给定元素v，查询v在哪一个集合当中。
    union(v1, v2): 给定元素v1和v2，将它们所在的集合合并为一个。

并查集通常用树形结构来表示。每一个集合是一棵多叉树，所以一组不相交集合构成了一个“forest”。比如{{1, 2, 3}, {4, 5}, {6}, {7}}这组不相交集合，可以用四棵树来表示:

1.    
   
2.    1           4       6         7
   
3.   / \         /
   
4.   2   3      5
   

复制代码

其中每棵树的root可以是这个集合中的任意元素（一般是第一个加入该集合的元素）。其他元素都是root的子node，或子node的子node……等等。

我们可以用root来代表集合本身。这样，当给定树中的任何一个节点，我们就希望能够快速地找到这个节点所在的集合，也就是树的root。所以，每个节点必须储存它的parent节点。但是反过来，我们不需要在已知root的情况下，查找树中的一个节点，所以并不需要储存child节点。也就是说，并查集树和普通的树恰好相反。

这样的话，find函数就很容易写了

1. find(v)
   
2.   while (v is not root)
   
3.         v = v->parent
   
4.   return v

复制代码

至于union函数，我们可以先找到两个节点所在的树的root，然后把较浅的树插入到较深的树中去。这样做的原因是希望得到的树能尽量平衡。为此，我们在每个节点中保存“以这个节点为root的树的深度”。如果树中只有root一个元素时，深度为0。

综合上述讨论，并查集树节点定义如下：

1. struct DJSetNode{
   
2.   int rank;
   
3.   DJSetNode* parent;
   
4.   DJSetNode(int r, DJSetNode* parent):
   
5.         rank(r), parent(p)
   
6.   {}
   
7. };

复制代码

这里的rank就是深度。之所以不叫“depth”，是因为以后我们可以对上述的并查集实现做进一步优化，称为Path Compression（本文不作讨论）。在作完这步优化以后，这个rank就和深度不对应了。

union函数可以实现如下：

1. union(v1, v2)
   
2.   root1 = find(v1)
   
3.   root2 = find(v2)
   
4.   if (root1 is root2)
   
5.     return root1
   
6.   if (root1 has lower rank)
   
7.     root2.parent = root1
   
8.     return root1
   
9.   else if (root2 has lower rank)
   
10.     root1.parent = root2
    
11.     return root2
    
12.   else // root1 and root2 have same depth
    
13.     root2.parent = root1
    
14.     root1.rank ++
    
15.     return root1
    

复制代码

----------------

在本题当中，我们可以将创建一个M x N的数组SEAMAP，类型为DJSetNode*。每次将一个坐标点(i, j)位置设为陆地时，我们做3件事：

1. 创建一个新的DJSetNode对象N
2. 将N作为一棵孤立的树插入到forest当中
3. 让SEAMAP[i, j]指向N

然后，我们查询SEAMAP[i, j]的四个邻位置。如果其中某些位置的值不为NULL，那么说明这里已经存在有岛屿，那么我们将N与那些位置所在的集合合并即可。对于四个邻位置，我们最多只要进行四次union操作即可。合并完成之后，forest中剩余的孤立树的个数即为孤立岛屿的个数。

由于并查集树都是平衡树，所以find和union都有O(logn)复杂度（其中n为岛屿位置的个数）。也就是说每添加一块岛屿，都仅需要O(logn)时间。

------------------
代码如下:

1. struct DJSetNode {
   
2.     int label;  // 保留字。本程序中并未用到。
   
3.     int rank;   // 在本程序中就是树的深度。
   
4.     DJSetNode* parent;
   
5.     DJSetNode(int lb, int r, DJSetNode* p): label(lb), rank(r), parent(p) {}
   
6. };
   
7. class Solution {
   
8.     unordered_set<DJSetNode*> forest;   // 包含当前所有树的根
   
9.    
   
10.     // MAKESET: 产生一个仅含一个元素的set，并将其作为一棵树加入forest
    
11.     DJSetNode* makeSet() {
    
12.         DJSetNode* cur = new DJSetNode(0, 0, nullptr);   
    
13.         forest.insert(cur);
    
14.         return cur;
    
15.     }
    
16. 
    
17.     // FIND: 给定任意一个元素，找到这个元素所在树的root
    
18.     DJSetNode* find(DJSetNode* n) {
    
19.         if (n == nullptr) return nullptr;
    
20.         while (n->parent) {
    
21.             n = n->parent;
    
22.         }
    
23.         return n;
    
24.     }
    
25. 
    
26.     // MERGE: 给定两个元素，合并这两个元素所在的树，并返回合并后树的root
    
27.     DJSetNode* merge(DJSetNode* n1, DJSetNode* n2) {
    
28.         DJSetNode* r1 = find(n1);   // 分别找到两元素所在的树的root
    
29.         DJSetNode* r2 = find(n2);
    
30.         if (r1 == r2) {             // 如果本来就在同一树，则不做任何事
    
31.             return r1;
    
32.         }
    
33. 
    
34.         if (r1->rank > r2->rank) {  // 如果树1的“深度”大于树2，
    
35.             r2->parent = r1;        // 则以树1为基础合并
    
36.             forest.erase(r2);       // 然后从forest中除去树2
    
37.             return r1;              // 这是为了保证合并后树的深度尽可能小
    
38.         }
    
39.         else if (r1->rank < r2->rank) { // 反之则以树2为基础合并，
    
40.             r1->parent = r2;
    
41.             forest.erase(r1);
    
42.             return r2;
    
43.         }
    
44.         else {                      // 若深度相同，则任选一树为基础合并
    
45.             r2->parent = r1;        // 此处选为树1
    
46.             forest.erase(r2);
    
47.             r1->rank++;             // 合并以后，树1的深度增加了1
    
48.             return r1;
    
49.         }
    
50.     }
    
51. 
    
52.     int add(const Point& p) {
    
53.         vector<DJSetNode*> nbs;     
    
54.         // 查看当前位置的四个邻点，如果为island，则将其加入队列
    
55.         if (p.x > 0 && seaMap[p.y][p.x-1]) nbs.push_back(seaMap[p.y][p.x-1]);
    
56.         if (p.y > 0 && seaMap[p.y-1][p.x]) nbs.push_back(seaMap[p.y-1][p.x]);
    
57.         if (p.x < NC-1 && seaMap[p.y][p.x+1]) nbs.push_back(seaMap[p.y][p.x+1]);
    
58.         if (p.y < NR-1 && seaMap[p.y+1][p.x]) nbs.push_back(seaMap[p.y+1][p.x]);
    
59. 
    
60.         DJSetNode* cur = makeSet(); // 先把当前加入的点看做一个新的孤立岛屿。
    
61.         seaMap[p.y][p.x] = cur;     //
    
62. 
    
63.         for (int i = 0; i < nbs.size();++i) {
    
64.             cur = merge(cur, nbs[i]);   // 将这个岛屿分别与周围的邻岛合并
    
65.         }
    
66.         return forest.size();       // 此时forest中的tree数就是孤立岛屿的数目
    
67.     }
    
68. public:
    
69.     vector<vector<DJSetNode*> > seaMap;
    
70.     int NR, NC;
    
71.     vector<int> numIslands2(int n, int m, vector<Point>& operators) {
    
72.         seaMap = vector<vector<DJSetNode*> >(m, vector<DJSetNode*>(n, nullptr));
    
73.         NR = m, NC = n;
    
74. 
    
75.         vector<int> res;
    
76.         //
    
77.         for (int i = 0; i < operators.size(); ++i) {
    
78.             int a = add(operators[i]);
    
79.             res.push_back(a);
    
80.         }
    
81.         return res;
    
82.     }
    
83. };

复制代码

------------------------------

以上关于并查集的内容参考自维基百科。

本文由stellari最先发表于1point3acres论坛，转载请注明出处。

1. /**
   
2. * Definition for a point.
   
3. * struct Point {
   
4. *     int x;
   
5. *     int y;
   
6. *     Point() : x(0), y(0) {}
   
7. *     Point(int a, int b) : x(a), y(b) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     /**
    
13.      * @param n an integer
    
14.      * @param m an integer
    
15.      * @param operators an array of point
    
16.      * @return an integer array
    
17.      */
    
18.     int find(int x, vector<int> &bin) {
    
19.             int r = x, y = x;
    
20.             while (r != bin[r]) {
    
21.                     r = bin[r];
    
22.             }
    
23.             while (y != r) {
    
24.                     int temp = bin[y];
    
25.                     bin[y] = r;
    
26.                     y = temp;
    
27.             }
    
28.             return r;
    
29.     }
    
30.     void merge(int x, int y, vector<int> &bin) {
    
31.             int fx = find(x, bin), fy = find(y, bin);
    
32.             if (fx != fy) bin[fx] = fy;
    
33.     }
    
34.     vector<int> numIslands2(int n, int m, vector<Point>& operators) {
    
35.         // Write your code here
    
36.         vector<int> bin(m * n, -1);
    
37.         vector<int> res(operators.size());
    
38.         int cur = 0;
    
39.         int dx[] = {0, 0, 1, -1};
    
40.         int dy[] = {1, -1, 0, 0};
    
41.         for (int i = 0; i < operators.size(); i ++) {
    
42.                 int x = operators[i].x, y = operators[i].y, temp = x * m + y;
    
43.                 if (bin[temp] != -1) continue;
    
44.                 bin[temp] = temp;
    
45.                 //cur ++;
    
46.                 set<int> hash;
    
47.                 //hash.insert(temp);
    
48.                 for (int j = 0; j < 4; j ++) {
    
49.                         int x1 = x + dx[j], y1 = y + dy[j], t = x1 * m + y1;
    
50.                         if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && bin[t] != -1) {
    
51.                                 int cnt = find(t, bin);
    
52.                                 if(hash.find(cnt) == hash.end()) hash.insert(cnt);
    
53.                         }
    
54.                 }
    
55.             for (int j = 0; j < 4; j ++) {
    
56.                 int x1 = x + dx[j], y1 = y + dy[j], t = x1 * m + y1;
    
57.                 if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && bin[t] != -1) {
    
58.                     merge(t, temp, bin);
    
59.                 }
    
60.             }
    
61.                 cur += 1 - hash.size();
    
62.                 res[i] = cur;
    
63.         }
    
64.         return res;
    
65.     }
    
66. };
    
67. 
    

复制代码

请问lz
题目给的是n行m列
为什么NR = m， NC = n？

blactangeri 发表于 2015-10-23 11:55
请问lz
题目给的是n行m列
为什么NR = m， NC = n？

是的，但是我个人认为Lintcode所用的这种定义方式不甚合理。视觉上来说，一般x,y应该“分别是在列和行方向上变动的数值”，也就是应该使用matrix[y][x]来调用(x, y)的值。但是Lintcode的调用方式却是matrix[x][y]。后者当然也可以，但是对我来说这样就不能用我熟悉的坐标方向来在头脑中具象化这一map，增大了我编程时的思维负担。因此我把调用方式换成了matrix[y][x]，相应地，m和n的定义也必须交换过来。

stellari 发表于 2015-10-24 09:21
是的，但是我个人认为Lintcode所用的这种定义方式不甚合理。视觉上来说，一般x,y应该“分别是在列和行方 ...

谢谢回复
我明白了 其实就是lintcode把矩阵给倒过来表示了

醉了，昨天面google onsite居然碰到了这个原题，而且前天晚上我基本就看了你这一篇面经 ==！ 真是谢谢了