数据结构 并查集

今天学习并查集，一种常用的树的算法，之后还会学习哈夫曼树

并查集：利用树型结构来处理一些不相交的集合的合并和查询问题

合并两个集合（两棵树）：只需要合并两棵树的根节点，先找到各自的根节点，把根节点设立父子关系即可

查询两个节点是否在同一个集合（树）：只需要找到两个节点的根节点，看根节点是否相同

并查集用树型结构实现：双亲表示法

并查集算法优化：路径压缩（递归实现）

例题：洛谷p1551—亲戚

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
class Tree_Node
{
public:
    int fi;
    int data;
public:
};
class Tree
{
public:
    int size;
    Tree_Node* pN;
public:
    Tree(int sz):size(sz)
    {
        pN = new Tree_Node[sz];
        for (int i = 0; i < sz; ++i)
        {
            pN[i].fi = pN[i].data = i + 1;
        }
    }
    int Find_fi(int k)//找祖先
    {
        while (pN[k - 1].fi != k)
        {
            k = pN[k - 1].fi;
        }
        return k;
    }
    int Find_fi_2(int k)//递归实现，实现路径压缩
    {
        if (pN[k - 1].fi == k)
        {
            return k;
        }
        else
        {
            //实现路径压缩
            pN[k - 1].fi = Find_fi_2(pN[k - 1].fi);//将双亲改为祖先
            return pN[k - 1].fi;
            //也可以写作return pN[k - 1].fi = Find_fi_2(pN[k - 1].fi);
        }
    }
};
int main()
{
    int n(0);
    int m(0);
    int p(0);
    cin >> n >> m >> p;
    Tree tr(n);
    int a(0);
    int b(0);
    int fa(0);
    int fb(0);
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        fa = tr.Find_fi_2(a);
        fb = tr.Find_fi_2(b);

        tr.pN[fa - 1].fi = fb;
    }
    for (int i = 0; i < p; ++i)
    {
        cin >> a >> b;
        if (tr.Find_fi_2(a) == tr.Find_fi_2(b))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}