[luoguP2147] [SDOI2008]Cave 洞穴勘测（并查集 || lct）

传送门

1.并查集骗分（数据太水，比正解还快。。。）

我们知道，并查集有一步操作叫“路径压缩”，但是本题的并查集我们不能路径压缩，否则就无法进行Destroy操作。那每一步操作我们应该怎么做呢？

对于Connect x y操作，先把x变成集合的根，之后root[x] = y;

对于Destroy x y操作，先把x变成集合的根，此时root[y]必然为x，令root[y] = y即可。

对于Query x y操作，看看x和y所在集合的根是不是一样的就好了。

那么如何把x变成集合的根呢？只要把从x到根路径上的每一条边反向即可，所以不能进行路径压缩。

其实并查集的解法也有用 lct 的思想的。

在这里，并查集中的两点之间的边就表示连接两个洞穴之间的边，非常的直接。。

注意一个细节 ： 题目中说——无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径

也就是说不会有环！这也正是能用并查集做的原因之一。

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define N 10001 4 5 int n, m; 6 int f[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 22 23 inline void make_root(int x, int c) 24 28 29 int main() 30 45 return 0; 46 }
View Code

2.lct（正解）

就是模板啦

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define N 10001 4 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) 5 6 int n, m; 7 int f[N], rev[N], son[N][2], s[N], size[N]; 8 9 inline int read() 10 17 18 inline bool isroot(int x) 19 22 23 inline int get(int x) 24 27 28 inline void pushdown(int x) 29 37 } 38 39 inline void rotate(int x) 40 53 54 inline void splay(int x) 55 64 65 inline void access(int x) 66 69 70 inline void reverse(int x) 71 76 77 inline int find(int x) 78 84 85 inline void link(int x, int y) 86 91 92 inline void cut(int x, int y) 93 99 100 int main() 101 115 return 0; 116 }
View Code

上一篇：[CODEVS1916] 负载平衡问题（最小费用最大流）

下一篇：[luoguP2342] 叠积木（并查集）

---

并查集 LCT