NC15808 任意点 [并查集]

题意

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

题解

如果n个点之间可以相互到达，则将n个点放入一个集合。所需添加的点数就是集合数-1
故：可以遍历所有点对，若彼此可达，则使用并查集将二者并到一起。
最后查询祖先为自身的点数，即树根数集合数。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int fa[maxn];                   //记录祖先节点
vector<pair<int,int>> a ;
int fi(int x){                  //find函数寻找祖先
    return x == fa[x] ? x : fa[x] = fi(fa[x]);
}

void un(int x,int y){           //union函数建立两点关系
    int p = fi(x);
    int q = fi(y);
    if(p != q) fa[p] = q;
}

int main()
{
    int n,m;
    cin>>n;
    a.resize(n);
    for(int i = 1;i <= n;++i) fa[i] = i;        //init
    for(int i = 1;i <= n;++i){
        scanf("%d%d",&a[i].first,&a[i].second);
    }
    for(int i = 1;i <= n;++i){
        for(int j = i + 1;j <= n;++j){
            if(a[i].first == a[j].first || a[i].second == a[j].second){
                un(i,j);
            }
        }
    }
    int cnt =0 ;
    for(int i = 1;i <= n;++i){
        if(fa[i] == i){
            cnt++;
        }
    }
    printf("%d\n",cnt-1);

    return 0;
}