Union Find with Undo

Takanori MAEHARA · web-flow · commit bd586ff14ffb · 2018-01-02T23:53:36.000+09:00
diff --git a/data_structure/!union_find_undo.cc b/data_structure/!union_find_undo.cc
@@ -20,81 +20,84 @@ using namespace std;
 #define snd second
 #define all(c) begin(c), end(c)
 
-struct undoable_union_find {
-  vector<int> p;
-  undoable_union_find(int n) : p(n, -1) { };
-  vector<tuple<int,int,int>> hist;
+
+struct UndoableUnionFind {
+  vector<int> parent; 
+  vector<tuple<int,int,int>> history;
+  UndoableUnionFind(int n) : parent(n, -1) { };
   bool unite(int u, int v) { 
-    if ((u = root(u)) == (v = root(v))) return false;
-    if (p[u] > p[v]) swap(u, v);
-    hist.push_back(make_tuple(u, v, p[v]));
-    p[u] += p[v]; p[v] = u;
+    u = root(u); v = root(v);
+    if (u == v) return false;
+    if (parent[u] > parent[v]) swap(u, v);
+    history.push_back(make_tuple(u, v, parent[v]));
+    parent[u] += parent[v]; parent[v] = u;
     return true;
   }
   void undo() {
-    int u, v, w; tie(u, v, w) = hist.back();
-    hist.pop_back();
-    p[v] = w;
-    p[u] -= p[v];
+    int u, v, w; 
+    tie(u, v, w) = history.back();
+    history.pop_back();
+    parent[v] = w;
+    parent[u] -= parent[v];
   }
   bool find(int u, int v) { return root(u) == root(v); }
-  int root(int u) { for (; p[u] >= 0; u = p[u]); return u; }
-  int size(int u) { return -p[root(u)]; }
+  int root(int u) { return parent[u] < 0 ? u : parent[u] = root(parent[u]); }
+  int size(int u) { return -parent[root(u)]; }
 };
 
-struct offline_dynamic_connectivity {
+
+struct OfflineDynamicConnectivity {
   int n;
-  undoable_union_find uf;
-  offline_dynamic_connectivity(int n) : n(n), uf(n) { }
+  UndoableUnionFind uf;
+  OfflineDynamicConnectivity(int n) : n(n), uf(n) { }
 
-  typedef pair<int,int> edge;
-  vector<edge> query;
+  typedef pair<int,int> Edge;
+  vector<Edge> query;
   vector<int> ans;
-  map<edge, vector<pair<int,int>>> appear;
+  map<Edge, vector<pair<int,int>>> appear;
 
-  void add_edge(int u, int v) {
+  void addEdge(int u, int v) {
     if (u > v) swap(u, v);
     appear[{u,v}].push_back({query.size(), 1<<30});
   }
-  void erase_edge(int u, int v) {
+  void eraseEdge(int u, int v) {
     if (u > v) swap(u, v);
     appear[{u,v}].back().snd = query.size();
   }
-  int is_connected(int u, int v) {
+  int isConnected(int u, int v) {
     query.push_back({u,v});
     return query.size()-1;
   }
-
-  vector<set<edge>> es;
-  void insert(int l, int r, int k, int s, int t, edge e) {
+  vector<set<Edge>> edges;
+  void insert(int l, int r, int k, int s, int t, Edge e) {
     s = max(s, l); t = min(r, t);
     if (s >= t) return;
     if (s == l && t == r) {
-      es[k].insert(e);
+      edges[k].insert(e);
     } else {
       insert(l, (l+r)/2, 2*k+1, s, t, e);
       insert((l+r)/2, r, 2*k+2, s, t, e);
-      if (es[2*k+1].count(e) && es[2*k+2].count(e)) {
-        es[2*k+1].erase(e);
-        es[2*k+2].erase(e);
-        es[k].insert(e);
+      if (edges[2*k+1].count(e) && edges[2*k+2].count(e)) {
+        edges[2*k+1].erase(e);
+        edges[2*k+2].erase(e);
+        edges[k].insert(e);
       }
     }
   }
   void rec(int l, int r, int k) {
     if (l >= r) return;
-    for (edge e: es[k]) uf.unite(e.fst, e.snd);
+    for (Edge e: edges[k]) uf.unite(e.fst, e.snd);
     if (l+1 == r) {
       ans[l] = uf.find(query[l].fst, query[l].snd);
     } else {
       rec(l, (l+r)/2, 2*k+1);
       rec((l+r)/2, r, 2*k+2);
     }
-    for (edge e: es[k]) uf.undo();
+    for (Edge e: edges[k]) uf.undo();
   }
   void solve() {
     int q = query.size();
-    es.resize(4*q);
+    edges.resize(4*q);
     for (auto a: appear) 
       for (auto b: a.snd) 
         insert(0, q, 0, b.fst, b.snd, a.fst);
@@ -104,15 +107,15 @@ struct offline_dynamic_connectivity {
 };
 
 int main() {
-  offline_dynamic_connectivity solver(3);
-  solver.is_connected(0,1);
-  solver.add_edge(0,1);
-  solver.is_connected(0,1);
-  solver.is_connected(1,2);
-  solver.add_edge(1,2);
-  solver.is_connected(0,2);
-  solver.erase_edge(0,1);
-  solver.is_connected(0,2);
+  OfflineDynamicConnectivity solver(3);
+  solver.isConnected(0,1);
+  solver.addEdge(0,1);
+  solver.isConnected(0,1);
+  solver.isConnected(1,2);
+  solver.addEdge(1,2);
+  solver.isConnected(0,2);
+  solver.eraseEdge(0,1);
+  solver.isConnected(0,2);
   solver.solve();
   for (int i = 0; i < solver.query.size(); ++i) {
     cout << solver.query[i].fst << " " << solver.query[i].snd << " " << solver.ans[i] << endl;
