前言：
✌ 作者简介：游坦之 ✌
🏆 大学软件工程在读，希望学到真本领，经世致用 🏆
📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
💬 人生格言：穷且益坚，老当益壮💬
🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。

并查集的核心

初始化

由于每一个点在最开始的时候都是离散的，所以必须对每一个点进行一个初始化的处理，让其变成一个独立的点。也就是让父亲数组f，的初始值设置i。

    for(int i=1;i<=n;i++)
    {
        f[i] = i;
    }

查找

查找3和4是不是属于同一集合，就是看他们是否拥有相同的祖先。如果点是一个离散的点，或者本身就是祖宗，那么他的上面没有了，直接返回自身的值即可，但若是上面还有，就需要继续网上走，这里的代码运用了一个优化，可以减少运行所需要的时间。即在找祖宗的时候更新祖宗。

int find(int t)
{
    if(t==f[t])
    {
        return t;
    }
    return f[t] = find(f[t]);    
}

合并

将两个没关系的点，合并在一个集合里。或者将两个没关系的集合，合并到一个集合里。如下图，本身是两个没关系的集合，因为元素4和元素6合并到了一起，所以两个集合就合并到了一起。

void unite(int t1,int t2)
{
    int f1 = find(t1);
    int f2 = findd(t2);
    f[f1] = f2;
}

牛刀小试

原题传送门

并查集顾名思义，并是合并的意思，查是查找的意思，集是集合的意思。

并查集定义：1.并查集是一种树的数据结构，用于处理一些不相交集合的合并以及查询是否在一个集合的操作。2.并查集通常包含两种操作：查找（find）函数用来查询两个元素是否在同一集合当中；合并（union）函数用来将两个元素合并为同一集合。

题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。

接下来 M 行，每行包含三个整数 Zi,Xi,Yi 。

当 Zi = 1 时，将Xi 与Yi 所在的集合合并。

当 Zi = 2 时，输出Xi 与Yi 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式
对于每一个Zi​=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入输出样例
输入
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出
N
Y
N
Y

说明/提示
对于 30% 的数据，N≤10，M≤20。

对于 70% 的数据，N≤100，M≤10^3。

对于100% 的数据，1≤N≤10^4，1≤M≤2×10^5，1≤Xi​,Yi​≤N，Zi​∈{1,2}。

#include <iostream>
using namespace std;
const int M = 10010;
int f[M];
int n,m;
int find(int t)
{
    if(t==f[t])
    {
        return t;
    }
    return f[t] = find(f[t]);    
}
void unite(int t1,int t2)
{
    f[find(t1)] = f[find(t2)];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f[i] = i;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a==2)
        {
            int t1 = find(b);
            int t2 = find(c);
            if(t1==t2)
            {
                cout<<"Y"<<endl;
            }else{
                cout<<"N"<<endl;
            }
        }else{
            unite(b,c);
        }
    }
    
    return 0;
}

✨$\textcolor{blue}{原创不易，为了最基础的欲望！}$ <br/>
👍 $\textcolor{green}{点赞，不会损失一匹布！}$ <br/>
⭐️ $\textcolor{green}{收藏，不会丢失一厘金！}$ <br/>
✏️ $\textcolor{green}{留下痕迹，却会温暖作者的心！}$ <br/>