任意点

题目链接：https://ac.nowcoder.com/acm/problem/15808
说到这道题，就介绍一道及其相似的题目--- 加边无向图
（链接：https://ac.nowcoder.com/acm/problem/14685）
任意点这道题是很明显的一道并查集的题目，用一个复杂度为O（logn）的遍历所有点，然后判断他们的横坐标是否相同，或者纵坐标是否相同，相同就归为一类中，最后去求有多少个独立的点区域，然后输出个数减1（因为n个区域只需要n-1个点就可以连通）。
并查集常用的merge操作和find操作就不谈了，注意点和详情直接看代码和注释。

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define ll long long
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
struct dot {
    int x;
    int y;
}a[105];
int fa[105];
int n;
//并查集常用操作 merge 与find
int find(int x) {  
    return(fa[x]==x?x:fa[x]=find(fa[x]));
}
void merge(int x, int y) { //将x 和y连通到一个区域网内
    fa[find(x)] = find(y);
}
//void my_input(void) {
//
//}
void solve(void) {
    cin >> n ;
    for (int i = 1;i <= n;i++) { fa[i] = i; }  //先使n个互相独立
    for (int i = 1;i <= n;i++) { // 将各个点存入数组a【i】；
        dot temp;
        cin >> temp.x >> temp.y;
        a[i] = temp;
    }
    for (int i = 1;i <= n;i++) {// 遍历将满足条件的点连通为一个区域内
        for (int j =i+ 1;j <= n;j++) {        
            if (a[i].x == a[j].x || a[i].y == a[j].y) merge(i, j); 
        }
    }
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        if (find(i) == i)cnt++;        // 计算独立的点区域的个数 
    }
    cout << cnt-1;  //n个区域网只需要n-1个点  即可连起来 
}
int main() {
    close_stdin;//只是为了让cin和printf一样快
    solve();
}

谢谢浏览哈！