重建元素矩阵

tag

并查集，图论

题意简述

给你一个 $n\times m$的网格图，一开始有 $q$ 个格子上被标记。对于任意两行两列，如果交汇的四个格子中有三个被标记，那么第 $4$ 个会被自动标记。问你至少需要手动标记几个格子，使得整个矩形内的格子都被标记。

题解思路

对于任意两行两列，如果交汇的四个格子中有三个被标记，那么第 $4$ 个会被自动标记。如果从图论的角度出发，我们可以把每个行和列看成一个点，交汇处的点看作边，那么实际上，对于第四个点的生成，实际上是四个点都位于一个连通块中。最后要让图上所有的格子都有点，实际上是要让所有的行，列都处于一个连通块中。每次操作，添加一个点，实际上就是把 $x$ 行和 $y$ 列所在的连通块合并。那么最少的操作次数就是目前有的连通块数量-1（即全部合并花费的次数）。

参考代码

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

signed main()
{
    IOS;
    int n, m, q;
    cin >> n >> m >> q;
    DSU dsu(n + m + 1);
    for(int i = 1; i <= q; i ++)
    {
        int x, y;
        cin >> x >> y;
        dsu.merge(x, y + n);
    }
    int ans = 0;
    for(int i = 1; i <= n + m; i ++) ans += dsu.f[i] == i;
    cout << ans - 1 << '\n';
    return 0;
}