如何将并查集（UnionFind）成的？
摘要：并查集和其他树形结构不一样，是由孩子指向父亲，它解决了一些连接问题，怎么才能确定两个点是否相连呢？并查集可以非常快的确定两个点是否连接。 如何确定连个点是否连接呢？ 我们可以用一个数组表示，对于0到9每个不同的编号可以表示不同的对象，这里可
并查集和其他树形结构不一样，是由孩子指向父亲，它解决了一些连接问题，怎么才能确定两个点是否相连呢？并查集可以非常快的确定两个点是否连接。
如何确定连个点是否连接呢？
我们可以用一个数组表示，对于0到9每个不同的编号可以表示不同的对象，这里可以看作一个点，而编号对应的不同的元素可以表示不同的集合，其中[0，2，4，6，8]表示一个集合。这样就可以表示连接问题了，0和2就是表示相连接，因为它们在一个集合，0和1因不在一个集合所以不连接。
对于一组数据并查集主要支持两个动作：
isConnected(p,q)：查询元素p和q是否在一个集合
unionElements(p,q)：合并元素p和q的集合
Code
#pragma once
class UF {
private:
virtual const int getSize() const noexcept = 0;
virtual bool isConnected(int p, int q) = 0;
virtual void unionElements(int p, int q) = 0;
};
#pragma once
#include "UF.h"
#include<cassert>
class UnionFind1 : public UF {
private:
int *id;
int size;
public:
UnionFind1(int capacity) {
id = new int[capacity];
size = capacity;
for (int i = 0; i < size; ++i) {
id[i] = i; //初始化不同的元素表示不同的集合都不相连
}
}
const int getSize() const noexcept {
return size;
}
//返回p所在的集合
int find(int p) {
assert(p >= 0 && p < size);
return id[p];
}
//判断是否相连
bool isConnected(int p, int q) {
return find(p) == find(q);
}
//合并集合
void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID) {
return;
}
for (int i = 0; i < size; ++i) {
if (id[i] == pID) {
id[i] = qID; //让两个集合都相同就行了
}
}
}
};
优化unionElements
从代码中可以看到：
unionElements的时间复杂度是O(n)
isConnected的时间复杂度是O(1)
将每个元素，看做是一个节点，每个节点指向它的父节点，而根节点指向自己。如果我们进行unionElements(4,3)操作，那么就是让4索引的元素为3。同在一个树下面就是同一个集合表示相连。