假设有一大堆人，这其中分了很多小群体。每个小群体都有自己的首领。比如a、b、c、d是一个小群体。其中a是头儿，b是a的下属，c和d都是b的下属。

那么我们可以这样写：b->a，表示b的上级是a。

c->b，d->b，表示c和d的上级都是b。

这其实就已经是并差集了。稍微抽象一下，字母替换为数字，用一个数组parents来记录元素之间的关系。parents[i]表示i的祖先是谁，当然优先级最高的祖先就是它自己，这样定义是比较科学的。

我们可以写出这样的结构：

1 vector<int> parents;//当然如果有n个元素，那么最开始要初始化nums[i]=i，i从0到n-1。
2 int getParent(int child)
3 {
4     return parents[child];
5 }

现在问题来了，如果有一个很长的序列，1是祖先，然后1是2的爹，2是3的爹，3是4的爹，以此类推到10000。

如果我们调用getParent(10000)，内部递归调用getParent(9999)、getParent(9998)等，直到getParent(1)返回1，之后10000层函数嵌套层层返回。不难想象这个复杂度。如果数据再大都可能会爆栈。

这就要求我们必须对路径进行压缩，毕竟我们调用getParent(10000)，其实并不想知道10000的父亲一直到他的最上面的祖先路径上的所有人，我们只想知道他的祖先是谁就够了。

所以我们在调用getParent(x)的时候，如果发现目前x的祖先不等于其自己，那么说明x可能还有更靠上的祖先。那么我们先去找到x最靠上的祖先，存好，再返回。

即我们的getParent()函数改成这样：

1 int getParent(int child)
2 {
3     if(child!=parents[child]){
4     //child自己如果是它们家族的祖先，那么parents[child]肯定等于child，既然不等，说明parents[child]不一定是真正祖先，为了确定我们还得往上找
5         parents[child]=getParent(parents[child]);//这里递归调用，返回child最靠上的祖先并更新parents[child]的值
6     }
7     return parents[child];
8 }

回到之前a、b、c、d的例子，经过路径压缩，我们得到parents[a]=a;　　parents[b]=a;　　parents[c]=a;　　parents[d]=a;

这样每个元素的查询时间变成了1次。数据量较大的时候，时间效率可以大大提高。

另外并差集还要支持一个性质：merge。即合并两个子集。这种情况现实中也大量存在，比如一个部门进行拆分，合并到另一个部门下面，那所有的人事档案也要一并移过去。这些人原来的boss是A，现在就都变成了B。

merge函数我们这样写：

1 void merge(int x, int y)
2 {
3     int px = getParent(x);
4     int py = getParent(y);
5     if(px != py)
6     {
7         parents[px] = py;   //parents[py]=px;也可以
8     } 
9 }

思路很简单，就是直接把一个元素的祖先置为另一个元素。你可能会说这样写不是把x简单的作为y的孩子。这样查询x和x的孩子的时间效率会很低。

没错，但我们之前写了路径压缩算法，只要我们调用一次getParent(x)，我们的算法就会把x的祖先更新为y最靠上的祖先。所以不必担心这个问题。