题目

来源：广州大学第十四届ACM大学生程序设计竞赛（同步赛）

Madeline 来到了镜之寺庙（Mirror Temple），镜之寺庙有很多红色的泡泡，可以通过这个红色泡泡穿梭到同一横坐标或者同一纵坐标的相邻红色泡泡。
为了简化模型，限定红色泡泡都在一个大小为 的二维空间内。总共有 个红色泡泡，第 个泡泡的位置是在。保证每两个红色泡泡都不在同一个位置，即对于所有 ， 或者 。
现在有 个询问，第 个是询问若 Madeline 一开始在第 个红色泡泡中，能不能通过一次或多次穿梭到达第 个红色泡泡中。（）

解题思路

原本使用 BFS 算法，然后超时。C++代码
因为有多次询问，使用上面的算***有许多重复计算。
例如：
3 个泡泡的位置

1 1000
1000 1
1000 1000

3 个询问

1 2
1 3
2 3

计算第 1 个询问时，路径为 1 -> 3 -> 2，在得出答案时，可以同时得出第 2 个和第 3 个询问的正确性。而在第 2、3 次中又重复计算了一遍。

通过上面的例子可以看出，这种从一个节点能到达另一个节点的关系具有传递性，即如果 a 能到达 b，b 能到达 c，那么 a 能到达 c。所有这种具有关系的节点属于同一个连通分量。因此，可以使用并查集来维护这种连通分量的关系。

构造并查集。横坐标相同或纵坐标相同的两个点属于同一个连通分量，对它们进行合并。
在每个询问中，判断 a 和 b 是否属于同一个连通分量，如果是，那么可到达，否则不能到达。

C++代码

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

const int maxn = 1e5+5;
vector<int> x[maxn];
vector<int> y[maxn];

class UnionFind {
    vector<int> parent;

public:
    UnionFind(int n) {
        parent.resize(n, 0);
        for(int i=0; i<n; ++i)
            parent[i] = i;
    }

    int find(int i) {
        if (i == parent[i]) {
            return i;
        }
        parent[i] = find(parent[i]);
        return parent[i];
    }

    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};

int main(){
    int n, q, a, b;
    scanf("%d%d", &n, &q);
    vector<vector<int>> bubbles(n, vector<int>(2));

    UnionFind uf(n);
    for(int i=0; i<n; ++i){
        scanf("%d%d", &a, &b);
        if(x[a].size() > 0)
            uf.unite(i, x[a][0]);
        if(y[b].size() > 0)
            uf.unite(i, y[b][0]);
        x[a].push_back(i);
        y[b].push_back(i);
    }

    while(q--){
        scanf("%d%d", &a, &b);
        if(uf.find(a-1) == uf.find(b-1))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}