【刷题】数据结构——并查集【模板】

并查集用于快速判断两个元素是否在同一个集合中。

用树的形式来表达各个集合的关系，一棵树上的所有点代表是同一个集合。
合并两结点的集合时，只需在两个结点的祖先建立一条边。
判断两结点是否在同个集合，只需看两个结点是否是同一个祖先。

同时利用递归可以进行路径压缩。

#include 
using namespace std;
const int N = 100005;
int n, m, p[N];

void init() {
    for (int i = 1; i <= n; i ++ ) p[i] = i;
}

int find(int x) { // 返回x的祖先 
    if (p[x] != x) p[x] = find(p[x]); // 路径压缩
    return p[x];
}


void merge(int a, int b) {
    p[find(a)] = find(b);
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= m; i ++ ) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M') {
            merge(a, b);
        }
        else {
            if (find(a) == find(b)) printf("Yesn");
            else printf("Non");
        }
    }
    return 0;
}