$$\color{Red}{合并集合 简单通透 三种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

p[x]存储了每个点的祖先节点，而应该初始化的时候都默认和节点自己一样，即自己是自己的祖先节点。
而find(x)是一个递归的函数，它返回了一个节点的祖先节点，还把这个查找路径上所有节点直接变成了祖宗节点的孩子。我们在合并两个集合的时候会让一个点的祖先节点赋值为另一个节点的祖先节点，类似于java中的继承关系，这样就将一个集合的节点和另一个集合合并起来。
实现原理
当一个节点的祖先节点不为自己的情况下，就递归调用find(p[x])，查询存储的祖先节点的祖先是谁，如果这个祖先的p[p[x]]仍然不等于自己，那么它还会继续递归寻找，最终当找到祖先节点，即节点a满足p[a] = a。则开始进行回溯，让前面递归调用的一个个节点的p[x]赋值为p[a]（和a)相等。即做到了把这个查找路径上所有节点直接变成了祖宗节点的孩子

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010, n, m;
    static int[] p = new int[N];

    static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        for (int i = 1; i <= n; i++)
            p[i] = i;
        for (int i = 0; i < m; i++) {
            String[] s2 = br.readLine().split(" ");
            String op = s2[0];
            int a = Integer.parseInt(s2[1]);
            int b = Integer.parseInt(s2[2]);
            a = find(a);
            b = find(b);
            if (op.equals("M")){
                p[a] = b;
            }
            else {
                if(a == b) System.out.println("Yes");
                else System.out.println("No");
            }
        }
    }
}

python3 代码

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

if __name__ == '__main__':
    n, m = map(int, input().split())
    p = [int(x) for x in range(n+10)]

    for i in range(m):
        op = input().split()
        a = int(op[1])
        b = int(op[2])
        if op[0] == 'M':
            p[find(a)] = find(b)
        else:
            if p[find(a)] == p[find(b)]:
                print('Yes')
            else:
                print('No')

C++代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int p[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m, a, b;
    char op[2];
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)  p[i] = i;
    while(m--)
    {
        scanf("%s%d%d", op, &a, &b);
        if(*op == 'M')  p[find(a)] = find(b);
        else
        {
            if(find(a) != find(b))  printf("No\n");
            else                    printf("Yes\n");
        }

    }

    return 0;
}