[Acwing] 1144. 连接格点 Kruskal

前言

和上一题差不多,都是需要先加入边 传送门 :

思路

因为是二维所以我们需要将他转换成一维 i ∗ j + k i*j+k i∗j+k

排序操作可以避免了,因为值就1和2 所以我们可以先计算1的值,之后计算2的值

最后计算出答案即可

CODE

int find(int x)
{
	if(p[x]!=x)return p[x] = find(p[x]);
	return p[x];
	
}

inline int merge(int a,int b)
{
	int fa = find(a);
	int fb = find(b);
	if(fa!=fb)
	{
		p[fa] =fb;
		return 1;
	}
	return 0;
}
void cal()
{

}

void solve()
{
	cin>>n>>m;
	for(int i=1;i>x1>>y1>>x2>>y2)
	{
		int a = (x1-1)*m +y1;
		int b = (x2-1)*m +y2;
		merge(a,b);
	}
	
	for(int i=1;i