并查集
并查集
并查集的使用是如下的场景 1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己 2）find(i)：查找i所在集合的代表元素，代表元素来代表i所在的集合 4）void union(a, b)：a所在集合所有元素 与 b所在集合所有元素 合并成一个集合 5）各种操作单次调用的均摊时间复杂度为O(1)
优化
- 扁平化(重要)
- 小挂大
扁平化 查询的时候把途经节点直接和根相连 用栈实现
int find(int x) {
stack<int> st;
while(fa[x] != x) {
x = fa[x];
st.push(x);
}
while (!st.empty()) {
fa[st.top()] = x;
st.pop();
}
return x;
}
递归实现
int find(int x) {
if(fa[x] != x) {
fa[x] = find(fa[x]);
}
return fa[x];
}
小挂大 合并时大小较小的一个集合连接到较大的集合(影响不大)
void merge(int x,int y) {
int fx = find(x),fy = find(y);
if(sz[fx] >= sz[fy]) {
sz[fx] += sz[fy];
fa[fy] = fx;
} else {
sz[fy] += sz[fy];
fa[fx] = fy;
}
}
理解
各种操作单次调用的均摊时间复杂度为O(1),即使数据量很大，证明略