任意点-并查集

题目描述

平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。

输入描述:

第一行一个整数n表示点数（ 1 <= n <= 100)。 第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。 y轴正方向为北，x轴正方形为东。

输出描述:

输出一个整数表示最少需要加的点的数目。

分析：

知识点：并查集。n个点，横坐标相同或者纵坐标相同则说明可以互相抵达，则这两个点可以连成一条路径，用遍历连完点后，得到 i 条完整的路径（单独一个点也是一条路径），则需要增加i-1个点。 例如上图，连完所有点后就得到了4条路径那么需要增加3个点

AC代码：

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
int n,x[1005],y[1005],fa[1005];
void init(){                    //初始化源头 
	for(int i=0;i<n;++i)
		fa[i]=i;
} 
int find(int i){                //找源头 
	if(fa[i]==i)
		return i;
	else{
 		fa[i]=find(fa[i]);		//压缩路径 
		return fa[i];
	}
}
void union_z(int i,int j){      //联合两点 
	int fa_i=find(i);
	int fa_j=find(j);
	fa[fa_i]=fa_j;
}
int main(){
    cin>>n;
    for(int i=0;i<n;++i)
        scanf("%d %d",&x[i],&y[i]);
    init();
    for(int i=0;i<n-1;++i)
   		for(int j=i+1;j<n;++j)
		    if(x[i]==x[j]||y[i]==y[j])
		    	union_z(i,j);
	for(int i=0;i<n;++i)
		find(i);                //再压缩一次路径（感觉还可以优化一下但是懒得想了） 
	sort(fa,fa+n);
	int flag=fa[0],count=0;
	for(int i=1;i<n;++i)        //计算联合过后有几条路径 
		if(fa[i]!=flag){
			flag=fa[i];
			count++;	
		}
	printf("%d",count);
}