[luoguP2342] 叠积木（并查集）

传送门

up[i] 表示一个木块上面有多少个

all[i] 表示整个连通块内有多少个

那么 一个木块下面的木块个数为 all[root[i]] up[i] 1

注意：up[i] 可以在 find 函数中维护，而 all[i] 不好维护，那么我们只需要祖先节点的 all[i] 表示整个连通块内木块的数目即可

　　　合并时也注意维护

——代码

1 #include <cstdio> 2 #include <iostream> 3 #define N 1000001 4 5 int n; 6 int f[N], up[N], all[N]; 7 8 inline int read() 9 16 17 inline int find(int x) 18 25 return f[x]; 26 } 27 28 int main() 29 47 else 48 53 } 54 return 0; 55 }
View Code

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

下一篇：[BZOJ2843] 极地旅行社（LCT）

---

并查集