forked from MaskRay/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
number-of-islands-ii.cc
39 lines (39 loc) · 1.01 KB
/
number-of-islands-ii.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Number of Islands II
class Solution {
int find(vector<int> &djs, int x) {
while (djs[x] >= 0) {
if (djs[djs[x]] >= 0)
djs[x] = djs[djs[x]];
x = djs[x];
}
return x;
}
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
map<int, int> mp;
vector<int> djs(positions.size(), -1);
int cnt = 0;
vector<int> ret;
for (auto &pos: positions) {
int x = pos.first, y = pos.second, p = n * x + y, id = mp.size();
mp[p] = id;
cnt++;
for (int d = 0; d < 4; d++) {
int x = pos.first + ((int[]){-1,0,1,0})[d], y = pos.second + ((int[]){0,1,0,-1})[d],
q = x * n + y;
if (0 <= x && x < m && 0 <= y < n && mp.count(q)) {
int v = find(djs, mp[q]), u = find(djs, id);
if (v != u) {
if (djs[v] > djs[u])
swap(v, u);
djs[v] += djs[u];
djs[u] = v;
cnt--;
}
}
}
ret.push_back(cnt);
}
return ret;
}
};