-
Notifications
You must be signed in to change notification settings - Fork 2
/
305.cpp
80 lines (80 loc) · 2.15 KB
/
305.cpp
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class DisjointSet {
private:
vector<int> parent;
vector<int> rank;
int groups;
int M;
int N;
public:
DisjointSet(int m, int n) {
M = m;
N = n;
parent.resize(M * N, -1);
rank.resize(M * N, 0);
groups = 0;
}
int anchorToNode(int x, int y) {
return x * N + y;
}
void addNode(int x, int y) {
int node = anchorToNode(x, y);
if (parent[node] != -1) return;
parent[node] = node;
groups++;
}
int _find(int node) {
if (parent[node] != node) {
parent[node] = _find(parent[node]);
}
return parent[node];
}
int find(int x, int y) {
int node = anchorToNode(x, y);
return _find(node);
}
void join(int x1, int y1, int x2, int y2) {
int node1 = anchorToNode(x1, y1);
int node2 = anchorToNode(x2, y2);
if (parent[node2] == -1) return;
int p1 = _find(node1);
int p2 = _find(node2);
if (p1 != p2) {
groups--;
if (rank[p1] > rank[p2]) {
parent[p2] = p1;
}
else if (rank[p1] < rank[p2]) {
parent[p1] = p2;
}
else {
parent[p2] = p1;
rank[p1]++;
}
}
}
int getGroup() {
return groups;
}
};
class Solution {
public:
vector<int> numIslands2(int m, int n, vector<vector<int>>& positions) {
vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
DisjointSet* disjointSet = new DisjointSet(m, n);
vector<int> res;
for (auto& position : positions) {
int x = position[0];
int y = position[1];
disjointSet->addNode(x, y);
for (auto& direction : directions) {
int _x = x + direction.first;
int _y = y + direction.second;
if (_x < 0 || _x >= m || _y < 0 || _y >= n) continue;
disjointSet->join(x, y, _x, _y);
}
int groups = disjointSet->getGroup();
res.push_back(groups);
}
return res;
}
};