并查集
1. 简介
并查集是一种高效的数据结构，常用来解决集合的合并和查找问题，常见于图论问题中。
2. 操作
2.1 构建
并查集一般构建为初始时每个节点所属的集合编号即为自己的节点编号。
// 初始化
int father[MAXN]; // father[i] 即为节点 i 所属的集合编号
void init(int n) {
for(int i = n; i; --i) {
father[i] = i;
}
}2.2 查找
并查集的高效之处在于在查找过程中压缩路径，从而实现压缩路径后查找的效率变为 O(1) 。
// 寻找并查集的根节点
int findfather(int x) {
return x == father[x] ? x : (father[x] = findfather(father[x]));
}2.3 合并
每次合并时只需将一个集合的根节点的 father 设为另一个集合的根节点。
// 合并并查集
void mergefather(int x, int y) {
father[father[x]] = father[y];
}【注】不是 father[x] = y ，father[x] 改变的只是 x 的根节点，而不是整个并查集的根节点，因为并查集本质是依靠其根节点来维护的，所以应该将并查集的根节点的 father 修改为已另一个集合的根节点，从而保证前一个集合被合并到了后一个集合中。
3. 模板
#include <bits/stdc++.h>
using namespace std;
#ifndef _DSF_
#define _DSF_
#define ll long long
#define MAXN 505
// 并查集
struct dsf {
ll father[MAXN]; // father[i] 即为节点 i 所属的集合编号
dsf() {}
//初始化
void init(ll n) {
for(ll i = n; i; --i) {
father[i] = i;
}
}
// 寻找并查集的根节点
ll findfather(ll x) {
return x == father[x] ? x : (father[x] = findfather(father[x]));
}
// 合并并查集(将 x 节点所在并查集合并到 y 节点所在并查集)
void mergefather(ll x, ll y) {
father[father[x]] = father[y];
}
};
#endif本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
文件存储
文件存储（Cloud File Storage，CFS）为您提供安全可靠、可扩展的共享文件存储服务。文件存储可与腾讯云服务器、容器服务、批量计算等服务搭配使用，为多个计算节点提供容量和性能可弹性扩展的高性能共享存储。腾讯云文件存储的管理界面简单、易使用，可实现对现有应用的无缝集成；按实际用量付费，为您节约成本，简化 IT 运维工作。