洛谷 P5089 [eJOI2018]元素周期表（二分图+并查集）

洛谷 P5089 [eJOI2018]元素周期表（二分图+并查集）

洛谷 P5089 [eJOI2018]元素周期表

题目大意

• n ∗ m n*m n∗m矩阵中已有若干点，只要有构成矩形（平行于坐标轴）的四个点中三个，就可以补充剩下一个，求把矩阵填满最少需要添加多少点。
• n , m ≤ 2 ∗ 1 0 5 n,mle2*10^5 n,m≤2∗105

题解

• 把行和列拆开看成二分图，发现每次添加点的操作，是在已经连通的三个点中把没连的边给连上，连通块的数量没有改变。
• 同时，不难发现任何一个连通块中剩下的边都是可以直接加上的。
• 现在需要把矩阵中所有点都填满，相当于所有的边都要连上，那么根据上面的结论，只需要加入最少的边使所有的点构成一个连通块即可，自然答案是连通块数量减 1 1 1。

代码

#include<cstdio>
using namespace std;
int f[400010];
int get(int x) {if(f[x] == x) return x;return f[x] = get(f[x]);
}
int main() {int n, m, q, i, x, y;scanf("%d%d%d", &n, &m, &q);for(i = 1; i <= n + m; i++) f[i] = i;for(i = 1; i <= q; i++) {scanf("%d%d", &x, &y);x = get(x), y = get(y + n);f[x] = y;}int s = 0;for(i = 1; i <= n + m; i++) if(get(i) == i) s++;printf("%d", s - 1);return 0;
}