@[toc]
简介
带权并查集是一种带有某种信息的并查集,即每个子节点都储存其自身与跟节点的关系,如路径长度等。定义一个带权并查集数组:
1 2 3 4
| struct{ int p; int data; }f[MAX];
|
这里关键的问题时带权并查集在合并和路径压缩时怎么做到状态更新呢?
合并
首先合并,除了普通的合并,只要加一条信息更新就行了(更新最终根节点)
1 2 3 4 5
| void merge(int i, int j) { f[i].p = j; update(f[j].data); }
|
路径压缩
关于路径压缩,先看代码
更新方式1
1 2 3 4 5 6 7 8
| int find(int x) { if (f[x].p == x) return x; f[x].p = find(f[x].p); f[x].data = f[f[x].p].data; return f[x].p; }
|
和普通的路径压缩相比,只是多了一行代码。因为第5行代码执行后,f[x].p已经是根节点,所以这样更新使得子节点的data直接是根节点的data了.
更新方式2
可以在先用ft记录自己的父节点,然后利用递归栈先进后出的性质自根节点向叶节点更新数据,比如代码中的data可以表示子节点到根节点的距离,然后自根向叶逐层更新。
1 2 3 4 5 6 7 8 9 10
| int find(int x) { if (f[x].p == x) return x; int ft = f[x].p; f[x].p = find(f[x].p); f[x].data = f[ft].data + 1;
return f[x].p; }
|
Q1银河英雄传说
原题传送门->洛谷P1196
这道题除了普通的并查集操作,还需要记录根节点到叶节点的距离来计算两个飞船间的飞船数,即答案就是飞船i到根节点距离和飞船j到根节点距离的差的绝对值-1,而且根节点要记录该集合的飞船数以此来在合并操作时更新子节点到根节点的距离。具体实现看丑丑的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include<iostream> #include<algorithm> #include<numeric> #include<string> #include<vector> #include<cmath> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) struct { int p, len, all;
}f[30001]; int find(int x) { if (f[x].p == x) return x; int ft = f[x].p; f[x].p = find(f[x].p); f[x].len += f[ft].len;
f[x].all = f[f[x].p].all; return f[x].p; } void merge(int i, int j) { f[i].p = j; f[i].len += f[j].all; f[j].all += f[i].all; } int main() { int t; cin >> t; for (int i = 1; i <= 30000; i++) { f[i].p = i; f[i].all = 1; f[i].len = 0; } while (t--) { char op; int i, j; cin >> op >> i >> j; int ip = find(i), jp = find(j);
if (op == 'M') merge(ip, jp);
else { if (ip != jp) cout << -1 << endl; else { cout << labs(f[i].len - f[j].len) - 1 << endl; } } } return 0; }
|