LGP5089题解

考试的一道题，考场上sb了没写出来，然后在两天后的英语课上胡出来了（

首先猜一个奇怪的结论：

对于元素 \((a,b)\)，看做连接第 \(a\) 列和第 \(b\)　行的一条边，那么如果一行和一列在同一个联通块内（第 \(x\) 行和第 \(y\) 列），那么 \((x,y)\) 处一定能通过核聚变生成，或本来就有一个元素。

证明：

考虑数学归纳法。

假设一行与一列之间一共有 \(2k-1\) 条边。

\(k=1\)

很明显，该点有一个元素。

2. \(k=2\)

假设三条边为 \((a,b)(b,c)(c,d)\)。

看一眼核聚变的规则，发现 \((a,d)\) 有一条边。

3. \(k>2\)

两个点之间有边的条件是存在一条长度为 \(3\) 的路径连接这两个点。

而结论 \(k=2\) 的情况说明长度为 \(3\) 边能变成一条长度为 \(1\) 的边，也就是这两个节点之间的距离减少了 \(2\)。

然后我们发现 \(2k-1 - 2(k-1) = 1\) 即两点间有边，也就是这一行和这一列连接在了一起。

证毕。

这个结论告诉我们，我们只需要将所有行和列连接在一起就行了。

所有我们只需要数有多少个联通块，数量-1即为答案。

code:

#include<cstdio>

const int M=2e5+5;

int n,m,q;bool vis[M<<1];

struct Edge{

	int to;Edge*nx;

}e[M<<1],*h[M<<1],*cnt=e;

inline void Add(const int&u,const int&v){

	*cnt=(Edge){v,h[u]};h[u]=cnt++;

	*cnt=(Edge){u,h[v]};h[v]=cnt++;

}

void DFS(int u){

	vis[u]=true;

	for(Edge*E=h[u];E;E=E->nx){

		int v=E->to;

		if(vis[v])continue;

		DFS(v);

	}

}

signed main(){

	register int i,u,v,ans=0;

	scanf("%d%d%d",&n,&m,&q);

	for(i=1;i<=q;++i){

		scanf("%d%d",&u,&v);

		Add(u,v+n);

	}

	for(i=1;i<=n+m;++i){

		if(!vis[i])DFS(i),++ans;

	}

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

}

巴特西

LGP5089题解

最新文章

热门文章