并查集算法

基本内容

并查集算法主要是解决图论中的动态连通性问题，下面首先介绍一下什么叫做动态连通性。
这里的连通是等价的，主要有下面几个性质：

自反性，结点和自身相连通；
对称性，结点p结点q连通，那么结点q和结点p连通；
传递性，结点p和结点q连通，结点q和结点r连通，那么结点p和结点r连通；

各个连通我们可以看做是一个个森林，在具体编码的时候我们可以用数组来表示这种结构，我们在编写代码的时候主要是编写两个函数，一个函数是将两个结点进行连通，另一个函数是判断两个结点是否连通。

具体的思路是：我们可以假设树的每个结点都有一个指针指向它的父结点，如果是根结点的话，这个指针指向它自己，这样的话我们可以开一个n个元素的数组，每一个元素索引代表一个结点，该元素的值就表示它的父结点，所以说该数组每个元素初始时的值都为它自身。
通过上面的想法，我们将两个结点连通的时候可以将一个结点的根结点连接到另一个结点的根结点上，这样就实现了连通。我们在判断两个结点是否连通的时候只要看两个结点的根结点是否是同一个就可以了。

具体实现代码如下：

public void union(int p,int q){
      int root_p=find(p);
      int root_q=find(q);
      if(root_q==root_p)
            return;
      //parent数组记录各个结点的父结点；
      parent[root_p]=root_q;
} 

//其中find函数的作用是寻找某个结点的根结点，代码如下：

public int find(int x){
      while(parent[x]!=x){
            x=parent[x];
      }
      return x;
}

//判断两个结点是否连通
public boolean check(int p,int q){
      int root_p=find(p);
      int root_q=find(q);
      return root_p==root_q;
}

并查集算法的基本内容就是上面的这些思想和代码，下面主要就是进行一些优化。

优化

通过分析我们可以发现运算时间主要花在find函数上，也就说我们的树的高度越大的话就会导致花更多的时间，所以我们在进行连通操作的时候应该尽可能的让树的高度较小。
第一种方式就是我们在连通的时候可以将小一点的树加到较大一点的树下面，这样就能避免头重脚轻，使得树更平衡一些。具体解决的方法是另外用一个size数组记录各个树的结点数，在进行连接的时候简单进行一下比较即可。代码如下：

public void union(int p, int q) {
    int root_p = find(p);
    int root_q = find(q);
    if (root_p == root_q)
        return;

    // 小树接到大树下面，较平衡
    if (size[root_p] > size[root_q]) {
        parent[root_q] = root_p;
        size[root_p] += size[root_q];
    } else {
        parent[root_p] = root_q;
        size[root_q] += size[root_p];
    }
}

第二种方式是进行路径压缩，具体的操作主要是在find函数中进行，代码入下：

public int find(int x){
      while(parent[x]!=x){
            parent[x]=parent[parent[x]];
            x=parent[x];
      }
      return x;
}