305. Number of Islands II

There is a good video talking about Union Find for dynamic connectivity problem.
https://www.youtube.com/watch?v=dxONo9jDbN8
And here is its improvement.
https://www.youtube.com/watch?v=SpqjfGTOriQ
The idea is, check each pointer and its neighbors. If the neighbor is water, then do nothing. Otherwise, find the roots for node itself and the neighbor. If they don’t have the same parent, then do union.

When I revisited the problem, I made mistake in
line 11&16: I computed the index by "i * m + j".
line 17&19: I ignored when the neighbor isn't water and union the islands when two islands is connected (Really don't know what I was thinking...).

1:  class Solution {  
2:  public:  
3:    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {  
4:      vector<int> res;  
5:      if (n == 0 || n == 0) return res;  
6:      vector<int> roots(m * n, -1);  
7:      vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
8:      int count = 0;  
9:      for (int k = 0; k < positions.size(); k++) {  
10:        count++;  
11:        int r = positions[k].first * n + positions[k].second;  
12:        roots[r] = r;  
13:        for (int l = 0; l < 4; l++) {  
14:          int i = positions[k].first + dir[l].first;  
15:          int j = positions[k].second + dir[l].second;  
16:          int nr = i * n + j;  
17:          if (i < 0 || i == m || j < 0 || j == n || roots[nr] == -1) continue;  
18:          int r1 = findIslands(roots, nr), r2 = findIslands(roots, r);  
19:          if (r1 != r2) {  
20:            count--;  
21:            roots[r1] = r2; // union the two islands  
22:          }  
23:        }  
24:        res.push_back(count);  
25:      }  
26:      return res;  
27:    }  
28:    int findIslands(vector<int> &roots, int id) {  
29:      while (roots[id] != id) {  
30:        // path compression: make every other node to point to its grandparent  
31:        roots[id] = roots[roots[id]];   
32:        id = roots[id];  
33:      }  
34:      return id;  
35:    }  
36:  };