个人理解：并查集就是对数据分块，并查找任意数据是否在同一块里面，用到的是‘‘标记"思想，在每一块中选一个队长，掌门，经理。。。。。总之这个特殊数据就代表了他所在的这一块，任意两数据比较他们的掌门就能知道是不是属于同一块了。查：就是寻找掌门；并：就是将寻找途中的人的上级都设为掌门；
实现：首先pre[i]装着i的上级，当p[i]=i的时候，他就是掌门；
查找掌门的代码：
int find(int root) {//查找root结点的掌门 int son,temp; while(root!=pre[root])//退出条件，自己的上级就是自己 root=pre[root];//寻找自己上级的上级 //此时，root就是原root的掌门了 while(son!=root) { temp=pre[son]; pre[son]=root;//将自己的上级设为掌门 son=temp;//继续找掌门，直到掌门出现 } return root;//掌门驾到~~ }
合并掌门代码:
void join(int root1，int root2) {//查找root1和root2的掌门，并且合并 int x=find(root1); int y=find(root2); if(x!=y)//此时x是root1的掌门，y是root2的 pre[x]=y;//将x的上级标为y，也就是说两帮派合并了 }
原文：https://www.cnblogs.com/qq2210446939/p/10849449.html