并查集

开始时让每个元素构成一个个单元素集合（注意初始化时应使每个元素各成一组）
按照一定顺序将属于同一组元素所在的集合合并
期间要反复查找一个元素在哪一个集合中

---

引入：
n个对象，查询某两个对象间是否有连通的路径
涉及查询与合并命令

• Quick Find
  数组存储，同一连通分量中的索引数组值相同
  find很方便O(1)
  union很复杂，因为要找到所有值相同的索引O(n)

  
  QF.jpg

• Quick Union
  树结构
  union就是树根的连接O(n)
  确定是树可能变很高，find就要消耗O(n)

  
  QU.jpg

• 带权优化(find O(lgN),union O(lgN)
  为了避免得到很高的树，合并时注意将小树作为大树的孩子
  利用额外数组来存树的高度
  这样得到的树深度不会超过lgN

  
  带权优化.jpg
  WQU.jpg

• 路径压缩

---

并查集：树型数据结构 处理不相交集合的合并以及查询问题

---

操作：查找，合并
设置father[i]数组表示元素i的父亲
查找一个元素的祖先可以用递归知道father[i]==i
但数据量过大时，树结构可能会退化成一条链，每次查找都将耗费O(n)
采用路径压缩：找到最久远的祖先时，把路上经过的所有子孙直接连到它的孩子处

并查集查找.jpg

int getFather(int u)
{
     if(father[u]!=u) father[u]=getFather(father[u]);
     return father[u];
}

---

还有一种while的写法

int getFather(int u)
{
     while(u!=father[u]){
           father[u]=father[father[u]];
           u=father[u];
     }
}

就是把u连到他父亲的父亲那里
再把u变成他父亲的父亲

---

将两个不相交的集合合并，相当于两棵树的合并
把一棵树的祖先变成另一棵树的孩子

void Union(int x,int y)
{
      int fx=getFather(x),fy=getFather(y);
      if(fx!=fy){
            father[fx]=fy;
      }
}

---

• 时间及空间复杂度（这段没太看懂）
  空间：O(n)
  单次操作的均摊时间:O(a(n)) a(n)是f(n)=A(n,n)的反函数 A(n,n)是阿克曼函数

---

• 应用

  
  percolation.jpg