C++ DFS与并查集两种解法

这是一个关于图(graph)的问题。矩阵每个点对于图的一个节点，每个图节点有前后左右四个不同方向。问题的目标是找到有几个全为1的连通域。那么两种解法，并查集和DFS。
DFS思路：

void dfsIslands(vector<vector<char>>& grid, unordered_map<int, bool>& visited, int size, int cur) {
    visited[cur] = true;
    int m = (int)grid.size(), n = (int)grid[0].size();
    int i = cur / size, j = cur % size;
    vector<vector<int>> direction = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    for (auto dir:direction) {
        int nexti = i + dir[0], nextj = j + dir[1];
        if (nexti >= m || nexti < 0 || nextj >= n || nextj < 0 || visited[nexti * size + nextj]) continue;
        if (grid[nexti][nextj] == '0') {
            visited[nexti * size + nextj] = true;
            continue;
        }
        dfsIslands(grid, visited, size, nexti * size + nextj);
    }
}
int solve(vector<vector<char>>& grid) {
    // write code here
    int m = (int)grid.size(), n = (int)grid[0].size(), size = max(m, n), res = 0;
    unordered_map<int, bool> visited;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '0' || visited[i * size + j]) {
                visited[i * size + j] = true;
                continue;
            }
            res++;
            dfsIslands(grid, visited, size, i * size + j);
        }
    }
    return res;
}

下面是并查集(union_find)的解法。并查集是一个高级数据结构，其定义每个节点有一个father，若一个集合里是连通的，那么该集合就会有共同的father。并查集有两个主要的函数，其一是找father点的函数，其二是合并的操作。代码细节如下：

class unionFind_islands {
private:
    vector<int> father, rank;
public:
    int count = 0;
    int m, n;

    unionFind_islands(vector<vector<char>>& grid) {
        m = (int)grid.size();
        n = (int)grid[0].size();
        father = vector<int> (m * n);
        rank = vector<int> (m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                father[i * n + j] = i * n + j;
                rank[i * n + j] = 1;
                if (grid[i][j] == '1') count++;
            }
        }
    }

    int findFather(int cur) {
        if (father[cur] == cur) return cur;
        return father[cur] = findFather(father[cur]);
    }

    void unionIslands(int i, int j) {
        int faA = findFather(i);
        int faB = findFather(j);
        if (faA == faB) return;
        count--;
        if (rank[faA] > rank[faB]) father[faB] = faA;
        else if (rank[faB] == rank[faA]) {
            father[faB] = faA;
            rank[faA]++;
        }
        else father[faA] = faB;
    }

};
int solve(vector<vector<char>>& grid) {
    unionFind_islands uf = unionFind_islands(grid);
    vector<vector<int>> direction = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    for (int i = 0; i < uf.m; i++) {
        for (int j = 0; j < uf.n; j++) {
            if (grid[i][j] == '1') {
                for (auto dir:direction) {
                    int nexti = i + dir[0], nextj = j + dir[1];
                    if (nexti < 0 || nexti >= uf.m || nextj < 0 || nextj >= uf.n) continue;
                    if (grid[nexti][nextj] == '1') uf.unionIslands(i * uf.n + j, nexti * uf.n + nextj);
                }
            }
        }
    }
    return uf.count;
}