# Not DFS nor BFS, but Disjoint Set in C++. 10ms solution

• I solved it in two ways, one is BFS, the other is Disjoint Set.

``````//Solution 2: 并查集
//            Disjoint set
//            time: O(n)
//            space: O(n)
//            10ms
class Solution {
public:
int nr_row, nr_col;
const int TYPE_WATER = 0x7fffffff;
int numIslands(vector<vector<char> > &grid) {
if (grid.empty() || grid[0].empty()) {
return 0;
}
nr_row = grid.size();
nr_col = grid[0].size();

int type_num = 0;
vector<int> type(nr_col + 1, TYPE_WATER); //type[k+1] => grid[x][k] type
unordered_map<int, int> table;            //并查集, disjoint set
for (int i = 0; i < nr_row; ++i) {
for (int j = 0; j < nr_col; ++j) {
int near_type = min(type[j], type[j+1]);
if (grid[i][j] == '1') {
if (type[j] != TYPE_WATER && type[j+1] != TYPE_WATER) {
int group1 = find_parent(table, type[j]);
int group2 = find_parent(table, type[j+1]);
table[max(group1, group2)] = min(group1, group2);
}
if (near_type == TYPE_WATER) {
type[j+1] = ++type_num;
table[type[j+1]] = type[j+1];
} else {
type[j+1] = near_type;
}
} else {
type[j+1] = TYPE_WATER;
}
}
}

unordered_set<int> s;
for (int i = 1; i <= type_num; ++i) {
s.insert(find_parent(table, i));
}
return s.size();
}

int find_parent(unordered_map<int, int> &table, int type) {
return table[type] == type ? type :
table[type] = find_parent(table, table[type]);
}
};
``````

And below is the normal BFS one:

``````//Solution 1: BFS广度优先遍历
//            time: O(n)
//            space: < O(n)
//            14ms
class Solution {
public:
struct Point {
int row, col;
Point(int _x, int _y) : row(_x), col(_y) {}
};
int nr_row, nr_col;
int numIslands(vector<vector<char> > &grid) {
if (grid.empty() || grid[0].empty()) {
return 0;
}

nr_row = grid.size();
nr_col = grid[0].size();

int res = 0;
queue<Point> q;

for (int i = 0; i < nr_row; ++i) {
for (int j = 0; j < nr_col; ++j) {
if (grid[i][j] == '0') {
continue;
}
++res;

grid[i][j] = '0';
q.push(Point(i, j));
while (!q.empty()) {
Point point = q.front();
q.pop();
}
}
}
return res;
}

void addNeighbor(vector<vector<char> > &grid, Point point,
int d_row, int d_col, queue<Point> &q) {
point.row += d_row;
point.col += d_col;
if (point.row >= nr_row || point.col >= nr_col ||
point.row < 0 || point.col < 0 ||
grid[point.row][point.col] == '0') {
return;
}
grid[point.row][point.col] = '0';

q.push(point);
}
};
``````

Feel free to visit: https://github.com/fanfank/leetcode

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.