并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

具体可以用于判断图的连通分量，用某一连通分量中的某节点的value表示整个连通分量，具有指向性，优势在于更新根节点后所有枝叶指向的根节点都更新，实质为将一棵树接为另一棵树的子树。可以用于构造最小生成树的Kruskal算法。

并查集的操作

1.初始化：让所有结点的根节点为他们本身

for(int i=1;i<=n;i++) v[i]=i;

2.合并：合并两个元素所属集合（合并对应的树）

基本形式（简单）

void unite(int x, int y)
{
	v[find(x)] = find(y);
}

3.查询：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

需要沿着树向上移动，直至找到根节点

int find(int x)
{
    return v[x] == x ? x : find(v[x]);
}

例题：

洛谷P1551P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 5000 + 10;
int n, m, p, x, y;
int v[N];
int find(int x)
{
    return v[x] == x ? x : find(v[x]);
}
void unite(int x, int y)
{
    v[find(x)] = find(y);
}
int main()
{
    fast;

    cin >> n >> m >> p;
    for(int i=1;i<=n;i++) v[i]=i;
    while (m--)
    {
        cin >> x >> y;
        unite(x, y);
    }
    while (p--)
    {
        cin >> x >> y;
        if (find(x)==find(y))
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}

洛谷P1536 P1536 村村通 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int n,m,v[N],ton[N],x,y;
int find(int x) {return v[x]==x?x:find(v[x]);} //并查集查询
void unite(int x,int y) {v[find(x)]=find(y);} //并查集合并
int main()
{
    fast;
    while(1)
    {
        cin>>n;
        if(n==0) return 0;
        cin>>m;
        int ans=0;
        memset(ton,0,sizeof(ton));
        for(int i=1;i<=n;i++) v[i]=i;
        while(m--)
        {
            cin >> x >> y;
            unite(x, y);
        }
        for(int i=1;i<=n;i++) v[i]=find(i); //用find(i)更新数组v，避免多次调用递归导致超时
        for(int i=1;i<=n;i++) ton[v[i]]++; //桶排序
        for(int i=1;i<=n;i++) if(ton[i]) ans++; //遍历得出连通分量的数量

        cout<<ans-1<<'\n';//连通分量减一即为最少需建设道路数目
    }
    return 0;
}