并查集
并查集是一种用于处理不相交集合的合并与查询问题的数据结构，在 C++ 中有着广泛的应用，以下是关于 C++ 中并查集的详细介绍：
基本概念
- 集合表示：并查集将每个集合用一棵树来表示，树中的节点代表集合中的元素，树根作为集合的代表元素。
- 合并操作：把两个集合合并为一个集合，通过将一个集合的树根连接到另一个集合的树根来实现。
- 查询操作：查询两个元素是否属于同一个集合，通过判断它们的树根是否相同来确定。
实现方式
- 数组实现
- 原理：用一个数组
parent来存储每个元素的父节点。初始化时，每个元素的父节点设为其自身，表示每个元素都在独立的集合中。合并操作时，将一个集合的根节点的父节点设置为另一个集合的根节点。查询操作时，通过不断查找元素的父节点，直到找到根节点，来判断两个元素是否在同一集合。 - 代码示例
- 原理：用一个数组
#include <iostream>
#include <vector>
class UnionFind {
private:
// 存储每个元素的父节点
std::vector<int> parent;
public:
// 初始化并查集
UnionFind(int n) : parent(n) {
for (int i = 0; i < n; ++i) {
// 初始时每个元素的父节点是它自己
parent[i] = i;
}
}
// 查找元素x的根节点
int find(int x) {
// 路径压缩，使查找路径上的节点直接连接到根节点
while (x!= parent[x]) {
// 路径压缩优化，将x的父节点更新为父节点的父节点
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
// 合并元素x和y所在的集合
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX!= rootY) {
// 将y的根节点设置为x的根节点
parent[rootY] = rootX;
}
}
// 判断元素x和y是否在同一集合
bool connected(int x, int y) {
return find(x) == find(y);
}
};
int main() {
// 初始化并查集，有5个元素
UnionFind uf(5);
// 合并元素1和2所在的集合
uf.unionSet(1, 2);
// 合并元素3和4所在的集合
uf.unionSet(3, 4);
// 输出元素1和2是否在同一集合，是则输出true，否则输出false
std::cout << "Are 1 and 2 connected? " << (uf.connected(1, 2)? "true" : "false") << std::endl;
// 输出元素1和3是否在同一集合，是则输出true，否则输出false
std::cout << "Are 1 and 3 connected? " << (uf.connected(1, 3)? "true" : "false") << std::endl;
return 0;
}
- 链表实现
- 原理：每个集合用一个链表来表示，链表的头节点作为集合的代表元素。合并操作时，将一个链表连接到另一个链表的尾部。查询操作时，遍历链表来判断两个元素是否在同一链表中。
- 代码示例
#include <iostream>
// 链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class UnionFind {
private:
// 存储每个元素所在链表的头节点
ListNode** heads;
public:
UnionFind(int n) {
// 初始化头节点数组
heads = new ListNode*[n];
for (int i = 0; i < n; ++i) {
// 每个元素初始时都有自己的链表，头节点为自己
heads[i] = new ListNode(i);
}
}
// 查找元素x所在链表的头节点
ListNode* find(int x) {
return heads[x];
}
// 合并元素x和y所在的集合
void unionSet(int x, int y) {
ListNode* headX = find(x);
ListNode* headY = find(y);
if (headX!= headY) {
// 将y所在的链表连接到x所在链表的尾部
ListNode* cur = headX;
while (cur->next!= nullptr) {
cur = cur->next;
}
cur->next = headY;
// 更新y所在链表的头节点为x所在链表的头节点
heads[y] = headX;
}
}
// 判断元素x和y是否在同一集合
bool connected(int x, int y) {
return find(x) == find(y);
}
~UnionFind() {
// 释放链表节点内存
for (int i = 0; i < n; ++i) {
ListNode* cur = heads[i];
ListNode* next;
while (cur!= nullptr) {
next = cur->next;
delete cur;
cur = next;
}
}
delete[] heads;
}
};
int main() {
// 初始化并查集，有5个元素
UnionFind uf(5);
// 合并元素1和2所在的集合
uf.unionSet(1, 2);
// 合并元素3和4所在的集合
uf.unionSet(3, 4);
// 输出元素1和2是否在同一集合，是则输出true，否则输出false
std::cout << "Are 1 and 2 connected? " << (uf.connected(1, 2)? "true" : "false") << std::endl;
// 输出元素1和3是否在同一集合，是则输出true，否则输出false
std::cout << "Are 1 and 3 connected? " << (uf.connected(1, 3)? "true" : "false") << std::endl;
return 0;
}
应用场景
- 连通性问题：如判断网络中的节点是否连通，城市之间的道路是否连通等。
- 图的最小生成树：在 Kruskal 算法中，用于判断边的两个端点是否在不同的连通分量中，以避免形成环。
- 社交网络分析：判断两个人是否在同一个朋友圈子中，或者将具有共同朋友的人划分到同一个社交圈子里。