什么是并查集（Disjoint-set）对于一个集合S={a1, a2, ..., an-1, an}，我们还可以对集合S进一步划分: S1,S2,...,Sm-1,Sm，我们希望能够快速确定S中的两两元素是否属于S的同一子集。举个栗子，S={0，1, 2, 3, 4, 5, 6}，如果我们按照一定的规则对集合S进行划分,假设划分后为S1={1, 2, 4}, S2={3, 6}，S3={0, 5}，任意给定两个元素，我们如何确定它们是否属于同一子集？某些合并子集后，又如何确定两两关系？基于此类问题便出现了并查集这种数据结构。并查集有两个基本操作：Find: 查找元素所属子集Union：合并两个子集为一个新的集合int find(int x){ if(x==pre[x]) return x; else return pre[x] = find(pre[x]);}void join(int x, int y){ int xx = find(x); int yy = find(y); if(xx!=yy) pre[yy] = xx;}