功能
①:合并两个集合
void merge(int a, int b) { f[Find(a)] = Find(b); }
②:查询某个元素的祖宗节点
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }
扩展
① 记录每个集合的大小(绑定到根节点)
int pa = Find(a); int pb = Find(b); if(){ s[pb] += s[pa] }
②每个点到根节点的距离(绑定到每一个元素身上)
int n, p[N], s[N], d[N]; //p[x] x的父亲节点 d[x] x到父节点的距离 s[x] 集合的大小 int Find(int x) { //距离查找 if (p[x] != x) { int root = Find(p[x]); d[x] += d[p[x]]; p[x] = root; } return p[x]; } int pa = Find(a); int pb = Find(b); if () { //距离更新 p[pa] = pb; d[pa] = s[pb]; s[pb] += s[pa]; }