题目描述

836.并查集
这个算法是主要是寻求两个数是否在一个集合中，或者是将两个数添加到一个集合中，初始的时候将数组p[i] = I,这样设置成他们自己，将两个数放在一个集合标准是p[a] =p[b]
，其中find函数算法的核心，find函数是寻找一个数的父子节点是谁，当两个数的父子节点相同就证明两个数在同个集合当中即find(a) = find(b)，find函数即使利用如果p[a]!=a,就p[a]=find(p[a]) 知道找到后return p[a],合并两个点的所在集合是p[find(a)] =find(b)

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<string>
using namespace std;
const int N = 100010;

int n,m;
int p[N];

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

    return p[x];
}

int main()
{
    cin>>n>>m;
    for(int i =1;i<=n;i++)
        p[i] =i;
    while(m--)
    {
        int a, b;
        string op;
        cin>>op>>a>>b;

        if(op =="M")    p[find(a)] =find(b);
        else
        {
            if(p[a] ==p[b])
                cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }

    return 0;



}