刷题day8

200. 岛屿数量
     已解答
     中等
     相关标签
     premium lock icon
     相关企业
     给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

咋说，比较简单，dfs秒了
但是这个也能用并查集做，就差不多吧，反正遍历挨个合并就行了练一下模板吧

const int N = 1e5 + 10;
int parent[N], size[N];

int find(x) {
    if (x != parent[x]) parent[x] = find(parent[x]);
    return parent[x];
}

int union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (size[ra] < size[rb]) {
        int t = ra; ra = rb; rb = t;
    }
    // 原来大的是rb，现在大的是ra，把小的挂到大的下面
    // 就是rb父=ra
    parent[rb] = ra;
    size[ra] += size[rb]
}