带权并查集有哪些操作,详细讲解一下,并写一下参考代码,并详细解释一下参考代码,并讲解一道带权并查集的例题。
时间: 2023-03-28 15:04:50 浏览: 262
带权并查集是一种数据结构,主要用于维护一些元素之间的关系。它可以支持以下操作:
1. 初始化:将每个元素看作一个单独的集合,每个集合的父节点为自己,权值为。
2. 查找:查找元素所在的集合,同时返回该元素到集合根节点的路径上所有节点的权值之和。
3. 合并:将两个集合合并成一个集合,合并时需要更新根节点的权值。
下面是一个简单的带权并查集的参考代码:
```c
const int MAXN = 100010;
int fa[MAXN], val[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
val[i] = ;
}
}
int find(int x) {
if (x == fa[x]) return x;
int root = find(fa[x]);
val[x] += val[fa[x]];
return fa[x] = root;
}
void merge(int x, int y, int w) {
int root_x = find(x), root_y = find(y);
if (root_x != root_y) {
fa[root_x] = root_y;
val[root_x] = val[y] - val[x] + w;
}
}
```
其中,init函数用于初始化,find函数用于查找,merge函数用于合并。下面是一道带权并查集的例题:
【题目描述】
给定一个无向图,每条边有一个权值,现在有m个询问,每个询问给定两个点x和y,求x到y的路径上的边权之和。
【解题思路】
我们可以使用带权并查集来维护每个点到根节点的路径上的边权之和。具体来说,我们可以将每个点看作一个集合,集合的根节点为该点到根节点路径上的最后一个点,集合的权值为该点到根节点路径上的边权之和。这样,我们就可以通过find函数来查找x和y所在的集合,并计算它们到根节点路径上的边权之和,最后将两个权值相减即可得到x到y的路径上的边权之和。
下面是该题的参考代码:
```c
const int MAXN = 100010;
int fa[MAXN], val[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) {
fa[i] = i;
val[i] = ;
}
}
int find(int x) {
if (x == fa[x]) return x;
int root = find(fa[x]);
val[x] += val[fa[x]];
return fa[x] = root;
}
void merge(int x, int y, int w) {
int root_x = find(x), root_y = find(y);
if (root_x != root_y) {
fa[root_x] = root_y;
val[root_x] = val[y] - val[x] + w;
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
init(n);
for (int i = 1; i <= m; i++) {
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
merge(x, y, w);
}
int q;
scanf("%d", &q);
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
if (find(x) != find(y)) printf("-1\n");
else printf("%d\n", val[x] - val[y]);
}
return ;
}
```
该代码的时间复杂度为O(m+qα(n)),其中α(n)为阿克曼函数的反函数,可以认为是一个很小的常数。
阅读全文