重建元素矩阵 tag 并查集，图论 题意简述 给你一个 $n\times m$的网格图，一开始有 $q$ 个格子上被标记。对于任意两行两列，如果交汇的四个格子中有三个被标记，那么第 $4$ 个会被自动标记。问你至少需要手动标记几个格子，使得整个矩形内的格子都被标记。 题解思路 对于任意两行两列，如果交汇的四个格子中有三个被标记，那么第 $4$ 个会被自动标记。如果从图论的角度出发，我们可以把每个行和列看成一个点，交汇处的点看作边，那么实际上，对于第四个点的生成，实际上是四个点都位于一个连通块中。最后要让图上所有的格子都有点，实际上是要让所有的行，列都处于一个连通块中。每次操作，添加一个点，实际上就是把 $x$ 行和 $y$ 列所在的连通块合并。那么最少的操作次数就是目前有的连通块数量-1（即全部合并花费的次数）。 参考代码 ```cpp 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; } ```