按秩合并并查集

coderhare · coderhare · commit 06bc5a92f6fe · 2022-05-02T21:02:21.000+08:00
diff --git a/tags/DataStructure/并查集.md b/tags/DataStructure/并查集.md
@@ -0,0 +1,52 @@
+# 并查集
+
+> 并查集是一类优雅的，解决连通块问题的数据结构
+
+### 并查集模板
+
+路径压缩+按秩合并版本
+
+```c
+template <class T>
+struct UF {
+    vector<T> rk;
+    vector<T> fa;
+    T count = 0;
+    UF (T n){
+        for(int i = 0; i < n; i++){
+            rk.push_back(1); fa.push_back(i);
+        }
+        count = n;
+    }
+    T find(T x){return fa[x] == x? x: (fa[x] = find(fa[x]));}
+    void merge(T x, T y){
+        x = find(x), y = find(y);
+        if(x != y) count--;
+        if(rk[x] <= rk[y]) fa[x] = y;
+        else fa[y] = x;
+        if(rk[x] == rk[y]) rk[y]++;
+    }
+    void isolate(T x){
+        if(x != fa[x]){
+            fa[x] = x;
+            count++;
+            rk[x] = 1;
+        }
+    }
+    T get() const {return count;}
+};
+```
+
+实测似乎在很多情况下都不会卡按秩合并，所以，也可以用更加简单的一个版本：
+
+```c
+int fa[100010];
+int find(int x){
+    return fa[x] == x? fa[x]: (fa[x] = find(fa[x]));
+}
+void merge(int x, int y){
+    fa[find(x)] = fa[find(y)];
+}
+```
+
+并查集可以快速解决连通块问题，计数连通块个数，确定一个区域的元素是否位于同一个连通块
