并查集

题意：

平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。
请问至少需要加多少个点，使得点对之间互相可以到达。
输入描述:
第一行一个整数n表示点数（ 1 <= n <= 100)。
第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。
y轴正方向为北，x轴正方形为东。
输出描述:
输出一个整数表示最少需要加的点的数目。

分析

这题就是考察并查集的。
首先我们如果直接从上下左右去判断一个点他能连接的点，不断地进行搜索的话，是比较麻烦的。
这里我们不妨这样做，我们先单看x轴和y轴。如果两个点x坐标相等那么他们就都在一个集合里。
同理如果两个点的y坐标相等那么他们以一点给在一个集合中。
那么我们可以断定一个点他的x坐标在一个集合，他的y坐标也在一个集合。
那么这两个集合是应该合并的。
我们不断这样，采取并查集的操作，最终仍然剩下来的集合数减一就是答案了。

代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>;
using namespace std;
typedef pair<int, int>pii;
const int max_n = 110;
int n;
pii a[max_n];
map<pii,pii> b;
int root[max_n * 2];
bool vis[max_n * 2];

int find(int x) {return (root[x] == x ? x : root[x] = find(root[x]));}

void merge(int x, int y) { root[find(x)] = find(y); }

bool cmp(pii p1, pii p2) { return p1.second < p2.second; }

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 0;i < n;i++)cin >> a[i].first >> a[i].second;
    for (int i = 0;i < n;i++)b[a[i]] = pii();
    sort(a, a + n);int j = 0;
    for (int i = 0;i < n;i++)
        if (i == 0 || a[i].first != a[i - 1].first) b[a[i]].first = j++;
        else b[a[i]].first = b[a[i - 1]].first;
    sort(a, a + n, cmp);
    for (int i = 0;i < n;i++)
        if (i == 0 || a[i].second != a[i - 1].second) b[a[i]].second = j++;
        else b[a[i]].second = b[a[i - 1]].second;
    for (int i = 0;i < j;i++)root[i] = i;
    //for (int i = 0;i < j;i++)cout << find(i) << "    ";cout << endl;
    for (int i = 0;i < n;i++)
        merge(b[a[i]].first, b[a[i]].second);
    for (int i = 0;i < j;i++)vis[find(i)] = true;
    //for (int i = 0;i < j;i++)cout << find(i) << "    ";cout << endl;
    int res = -1;
    for (int i = 0;i < j;i++)
        if (vis[i])res++;
    cout << res << endl;
}