Merge pull request #347 from hitonanode/rename-potentialized-unionfind

hitonanode · web-flow · commit 41af68b70d3c · 2024-10-03T00:08:35.000+09:00
WeightedUnionFind -&gt; PotentializedUnionFind
diff --git a/unionfind/potentialized_unionfind.hpp b/unionfind/potentialized_unionfind.hpp
@@ -3,12 +3,11 @@
 #include <utility>
 #include <vector>
 
-// CUT begin
-// Weighted UnionFind
-template <class S> struct WeightedUnionFind {
+// Potentialized UnionFind (Weighted UnionFind)
+template <class S> struct PotentializedUnionFind {
     std::vector<int> par, sz;
     std::vector<S> pot;
-    WeightedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) {
+    PotentializedUnionFind(int N = 0) : par(N), sz(N, 1), pot(N) {
         std::iota(par.begin(), par.end(), 0);
     }
     int find(int x) {
diff --git a/unionfind/potentialized_unionfind.md b/unionfind/potentialized_unionfind.md
@@ -1,6 +1,6 @@
 ---
-title: Weighted UnionFind （重み付き UnionFind）
-documentation_of: ./weighted_unionfind.hpp
+title: Potentialized UnionFind （重み付き UnionFind）
+documentation_of: ./potentialized_unionfind.hpp
 ---
 
 2個の要素間の重みづけが可能な UnionFind．
@@ -10,7 +10,7 @@ documentation_of: ./weighted_unionfind.hpp
 ポテンシャルが（ふつうの）整数の場合．
 
 ```cpp
-WeightedUnionFind<int> uf(N);
+PotentializedUnionFind<int> uf(N);
 uf.unite(s, t, diff);  // f[t] = f[s] + diff を要請．これまでの要請と矛盾すれば false を返す．
 
 auto x = uf.diff(s, t);  // f[t] - f[s] （として考えられる値の一つ）を出力．
@@ -19,9 +19,10 @@ auto x = uf.diff(s, t);  // f[t] - f[s] （として考えられる値の一つ
 ポテンシャルが $\mathbb{F}_{2}$ 上のベクトルの場合．
 
 ```cpp
-WeightedUnionFind<Nimber> uf(N);
+PotentializedUnionFind<Nimber> uf(N);
 ```
 
 ## 問題例
 
 - [No.1420 国勢調査 (Easy) - yukicoder](https://yukicoder.me/problems/no/1420) $\mathbb{F}_2$ 上のベクトル．
+- [AtCoder Beginner Contest 373 D - Hidden Weights](https://atcoder.jp/contests/abc373/tasks/abc373_d)
diff --git a/unionfind/test/potentialized_unionfind.test.cpp b/unionfind/test/potentialized_unionfind.test.cpp
@@ -1,12 +1,12 @@
-#include "../weighted_unionfind.hpp"
+#include "../potentialized_unionfind.hpp"
 #include <iostream>
 #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_B&lang=jp"
 using namespace std;
 
 int main() {
     int N, Q, x, y, z;
     cin >> N >> Q;
-    WeightedUnionFind<int> uf(N);
+    PotentializedUnionFind<int> uf(N);
     for (int i = 0; i < Q; i++) {
         int c;
         cin >> c;
diff --git a/unionfind/test/potentialized_unionfind_F2.yuki1420.test.cpp b/unionfind/test/potentialized_unionfind_F2.yuki1420.test.cpp
@@ -1,7 +1,7 @@
 #define PROBLEM "https://yukicoder.me/problems/no/1420"
 #define ERROR 1 // Check only whether the answer is -1 or not
 #include "../../number/nimber.hpp"
-#include "../weighted_unionfind.hpp"
+#include "../potentialized_unionfind.hpp"
 #include <iostream>
 using namespace std;
 
@@ -10,7 +10,7 @@ int main() {
     int N, M;
     cin >> N >> M;
 
-    WeightedUnionFind<Nimber> uf(N);
+    PotentializedUnionFind<Nimber> uf(N);
     while (M--) {
         int a, b, y;
         cin >> a >> b >> y;
diff --git a/unionfind/test/potentialized_unionfind_int.aoj3142.test.cpp b/unionfind/test/potentialized_unionfind_int.aoj3142.test.cpp
@@ -1,5 +1,5 @@
 #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3142"
-#include "../weighted_unionfind.hpp"
+#include "../potentialized_unionfind.hpp"
 #include <algorithm>
 #include <iostream>
 #include <vector>
@@ -8,7 +8,7 @@ using namespace std;
 int N;
 vector<vector<int>> to;
 vector<int> A, B;
-WeightedUnionFind<long long> uf;
+PotentializedUnionFind<long long> uf;
 
 long long dfs(int now, int prv) {
     long long acc = B[now] - A[now];
@@ -26,7 +26,7 @@ int main() {
     cin.tie(nullptr), ios::sync_with_stdio(false);
 
     cin >> N;
-    uf = WeightedUnionFind<long long>(N);
+    uf = PotentializedUnionFind<long long>(N);
     to.resize(N);
 
     for (int e = 0; e < N - 1; e++) {
