并查集

恶灬心 · 2018-09-23 10:17:06 · 个人记录

• 并查集操作

  1. 1.查：从当前结点查询至根节点。

     int find(int x)
     {
     return (x==a[x].f?x:a[x].f=find(a[x].f));
     }

  2. 2.并：将两个树合并成一棵树，操作则为将两个树的根节点相连。

     void union(int x, iny y)
     {
     fx=find(x),fy=find(y);
     if(fx!=fy) f[fx]=fy;
     }    

• 扩展

• 路径压缩

  对于不相交集合的操作，一般采用两种启发式优化的方法：

  1. 按秩合并：使包含较少结点的树根指向包含较多结点的树根。
  2. 路径压缩：使路径查找上的每个点都直接指向根结点。

在大多数场景中，路径压缩就能满足时间要求。

时间复杂度 对于有nn项，mm次操作的并查集（其中有ff次查询），运行时间时间复杂度为：

1. 朴素的并查集：O(n2)
2. 带按秩合并的并查集：O(mlgn)
3. 带路径压缩的并查集：O(n+f⋅(log2+f/nn))
4. 带路径压缩的按秩合并并查集：O(mα(n)) 其中α(n)α(n)为Ackerman函数反函数，对于实际运用中，可认为α(n)≤4