Number of Islands UnionFind
(書くまでpin留め)
code:solution.cpp
class UnionFind {
public:
UnionFind(vector<vector<char>>& grid) {
cnt = 0;
int m = grid.size();
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
parent.push_back(i*n + j);
cnt++;
}
else parent.push_back(-1);
rank.push_back(0);
}
}
}
int find_root(int i) {
if (parenti != i) parenti = find_root(parenti); }
void Union(int x, int y) {
int rootx = find_root(x);
int rooty = find_root(y);
if (rootx != rooty) {
else {
}
cnt--;
}
}
int getCnt() const {
return cnt;
}
private:
vector<int> parent, rank;
int cnt;
};
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
if (!m) return 0;
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
UnionFind uf(grid);
int ans = 0;
for (int y=0; y<m; y++) {
for (int x=0; x<n; x++) {
for (auto dir : dirs) {
int ny = y+dir0, nx = x+dir1; if (ny < 0 || m <= ny || nx < 0 || n <= nx) continue;
if (gridnynx == '1') uf.Union(y*n+x, ny*n+nx); }
}
}
}
return uf.getCnt();
}
};