并查集

n个互不相交的集合—等价关系划分—一个集合用一个树表示

数据结构与处理：pre数组+find函数+join函数+一个优化

• pre函数包含所有的元素：pre[i]记录的是第i个元素的parent；root是集合的标签，也是一个元素，标签身份的标志就是：parent是自己
• find函数：找到元素对应的标签：往上翻parent，直到找到parent是自身的root
• join函数：合并两个集合：将其中一个root的parent修改为另一个即可
• 路经压缩算法：每个元素的parent直接设为root