[eJOI2018]元素周期表

题目

\((r_1,c_1),(r_2,c_1),(r_1,c_2)\)三个格子存在就说明\((r_2,c_2)\)存在，如果我们将\(r_1,c_2,c_1,r_2\)都看成一些点的话，那么这个关系就非常类似于\(r_1\)和\(c_1\)联通，\(r_2\)和\(c_1\)联通，\(c_2\)和\(r_1\)联通，那么就说明\(r_2\)和\(c_2\)联通

于是我们将每个格子\((x,y)\)看成一些边，连接\(x\)行和\(y\)列，显然这张图是一个二分图，我们的目标就是将其补成一个完全二分图，即有\(n\times m\)条边

我们把已经有的\(q\)条边连上，发现我们不需要代价就能连的边都是在同一个联通块里的，我们补全所有不需要代价的边最多也只能把图补成几个完全二分图的子图

而同一个联通块内的边不需要代价，所以我们利用尽量少的边使得这张图完全联通就好了，显然需要连得边数就是联通块的个数\(-1\)，并查集维护一下就好了

代码

#include<bits/stdc++.h>

#define re register

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=2e5+5;

int fa[maxn<<1],n,m,q;

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

inline void merge(int x,int y) {

	int xx=find(x),yy=find(y);

	if(xx==yy) return;fa[xx]=yy;

}

int main() {

	n=read(),m=read(),q=read();

	for(re int i=1;i<=n+m;++i) fa[i]=i;

	for(re int x,y,i=1;i<=q;i++)

		x=read(),y=read(),merge(x,y+n);

	int ans=0;

	for(re int i=1;i<=n+m;i++) if(find(i)==i) ans++;

	printf("%d\n",ans-1);

	return 0;

}

巴特西

[eJOI2018]元素周期表

最新文章

热门文章