【数据结构】并查集

并查集找格子图的连通分量

int n, m;
    char g[1005][1005];

    int fa[1000005];
    int cnt[1000005];
    int id[1005][1005];
    int x[1000005];
    int y[1000005];

    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if(x == y)
            return;
        fa[x] = y;
        cnt[y] += cnt[x];
    }

    void init() {
        int N = n * m;
        for(int i = 1; i <= N; ++i) {
            fa[i] = i;
            cnt[i] = 1;
        }
        int top = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                ++top;
                id[i][j] = top;
                x[top] = i;
                y[top] = j;
            }
        }
    }

    int dx[] = {0, 0, -1, 1};
    int dy[] = {-1, 1, 0, 0};

    char ans[1005][1005];

    void Read() {
        if(scanf("%d%d", &n, &m) == -1)
            exit(0);
        for(int i = 1; i <= n; ++i)
            scanf("%s", g[i] + 1);
    }

    void Solve() {
        init();
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if(g[i][j] == '*')
                    continue;
                for(int k = 0; k <= 3; ++k) {
                    int X = i + dx[k];
                    int Y = j + dy[k];
                    if(1 <= X && X <= n && 1 <= Y && Y <= m && g[X][Y] == '.') {
                        merge(id[X][Y], id[i][j]);
                    }
                }
            }
        }
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                if(g[i][j] == '*') {
                    vector<int> r;
                    int res = 1;
                    for(int k = 0; k <= 3; ++k) {
                        int X = i + dx[k];
                        int Y = j + dy[k];
                        if(1 <= X && X <= n && 1 <= Y && Y <= m && g[X][Y] == '.') {
                            int tr = find(id[X][Y]);
                            int suc = 1;
                            for(int &ri : r) {
                                if(tr == ri) {
                                    suc = 0;
                                    break;
                                }
                            }
                            if(suc) {
                                r.push_back(tr);
                                res += cnt[tr];
                            }
                        }
                    }
                    ans[i][j] = res % 10 + '0';
                } else {
                    ans[i][j] = '.';
                }
            }
        }
        for(int i = 1; i <= n; ++i)
            puts(ans[i] + 1);
    }