并查集（Union-Find），又称不相交集合数据结构，是一种用于处理集合合并和查询问题的数据结构。它通常用于解决元素之间的分组问题，如连通分量问题、集合划分等。

并查集主要支持两种操作：

1. Union（合并）：将两个不相交的集合合并成一个集合。
2. Find（查询）：确定元素属于哪个集合，或者找到某个集合的代表元素。

通常情况下，并查集包括以下几个基本操作和概念：

• 初始化：初始化并查集，通常将每个元素视为一个独立的集合，即每个元素是其自身的代表。

• Find 操作：用于查找元素所属的集合，通常通过沿着父节点链向上查找，直到找到代表元素（根节点）。这个操作通常包括路径压缩，即将路径上的每个节点都直接连接到根节点，以优化查询操作的性能。

• Union 操作：用于合并两个不相交的集合，通常通过将其中一个集合的根节点指向另一个集合的根节点，或者将其中一个根节点连接到另一个根节点。

在实际应用中，你可以使用一个数组或向量来表示并查集的元素，其中数组的索引表示元素，数组的值表示该元素的父节点。初始状态下，每个元素的父节点是自身。

应用场景： 并查集主要用于解决元素的分组问题，例如：

1. 连通分量问题：在图论中，用于查找图中的连通分量，即图中的不相交子图。
2. 集合划分问题：将一个元素集合分为若干个不相交的子集。
3. Kruskal 算法：用于构建最小生成树。
4. 网络连接问题：查找网络中的连接关系。
5. 解决运算的等价关系：如解决数学等价关系问题。
6. 分组问题：将元素分为不相交的组。

基本思想： 并查集的基本思想是用树结构表示集合，每个树的根节点表示集合的代表元素。合并操作即将两个树合并成一个，查询操作即查找元素所在的集合根节点。路径压缩是一种优化方法，通过将查找路径上的每个节点直接连接到根节点，可以显著提高查询操作的效率。

并查集是一种高效且容易实现的数据结构，适用于解决多种实际问题中的分组和连接关系问题。 P3367

cpp
#include <iostream>
#include <vector>

using namespace std;

vector<int> parent; // Parent array for Union-Find

// Initialize the Union-Find data structure with n elements
void initialize(int n) {
    parent.resize(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i; // Each element is initially its own parent
    }
}

// Find the root (representative) of the set to which element x belongs
int find(int x) {
    if (x == parent[x]) {
        return x; // x is the root of its set
    }
    return parent[x] = find(parent[x]); // Path compression for optimization
}

// Union (merge) the sets to which elements x and y belong
void unite(int x, int y) {
    x = find(x); // Find the root of x's set
    y = find(y); // Find the root of y's set

    if (x != y) {
        parent[x] = y; // Make one of them the parent of the other
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    initialize(n); // Initialize Union-Find with n elements

    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            unite(x - 1, y - 1); // Adjust for 0-based indexing
        } else if (op == 2) {
            int root_x = find(x - 1);
            int root_y = find(y - 1);
            if (root_x == root_y) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    }

    return 0;
}