分析
由于竖向连接的花费更小,所以先竖着把所有的点进行并查集操作,之后再横着进行并查集操作。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m,x_1,y_1,x_2,y_2,idx;
int fa[N*N];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int ans;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n*m;i++) fa[i]=i;
while(cin>>x_1>>y_1>>x_2>>y_2) //把有关系的点事先联系起来,合并集合
{
int a=(x_1-1)*m+y_1;
int b=(x_2-1)*m+y_2;
int faa=find(a),fbb=find(b);
fa[faa]=fbb;
}
for(int i=0;i<n-1;i++) //竖向并查集
{
for(int j=1;j<=m;j++)
{
int a=i*m+j,b=(i+1)*m+j;
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
fa[faa]=fbb;
ans+=1; //每次合并答案+1
}
}
}
for(int i=0;i<n;i++) //横向合并并查集
{
for(int j=1;j<=m-1;j++)
{
int a=i*m+j,b=i*m+j+1;
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
fa[faa]=fbb;
ans+=2; //每次合并答案+2
}
}
}
cout<<ans;
return 0;
}