---
title: "合并集合"
created: 2025-11-28
tags:
  - 算法
---

# 合并集合

## 题目 [合并集合](https://www.acwing.com/problem/content/838/)

![[image-5390f5c6.png]]

## 思路分析

用一个数组去记录各点的祖宗结点是什么 下标标识各个点本身

一开始 所有点都是独立的 就把各下标对应的father都设为本身

要使某点从属入某集合 就直接在该点的fa[]存放另一结点

当然 优化时做了 数组中不记录直接父节点 而是记录祖宗结点

所以在进行合并操作时 要先进行find操作 找到祖宗结点

再把祖宗结点插入到另一个集合的祖宗结点下 实现合并

fa[find(a)]=find(b); 而判断两个结点是否从属一个集合

要做的就是比较一下祖宗结点是否相等

if(find(a)==find(b))

显然核心就在于这个find()

//返回x所在集合的编号（祖宗结点）

`int find(int x) {`

`if(fa[x]!=x)`

`fa[x]=find(fa[x]);//路径压缩优化`

`return fa[x];`

`}`

递归的过程中 让直接存上祖宗结点

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=100010;

int fa[N];

//返回x所在集合的编号（祖宗结点）

int find(int x)

{

    if(fa[x]!=x)

        fa[x]=find(fa[x]);//路径压缩优化

    return fa[x];

}

int main()

{

    int n,m;

    cin>>n>>m;

    for(int i=1;i<=n;i++)

    {

        fa[i]=i;//初始化 让父节点指向自己

    }

    while(m--)

    {

        char op[2];

        int a,b;

        cin>>op>>a>>b;

        if(op[0]=='M')

        {

            fa[find(a)]=find(b);//让a的祖宗结点等于b的祖宗结点 把a插在b里面

        }

        else

        {

            if(find(a)==find(b))

                cout<<"Yes"<<endl;

            else

                cout<<"No"<<endl;

        }

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[并查集|并查集]] 🏠 [[00-听课板子]] ➡️ [[堆|堆]]