leetcode

commit cb8c0714d657254df7e7eaa6653407d969920bf9
parent 4f3f21b33b22554b5b0901b97eab1d5d9cf191ce
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue,  3 Jan 2023 19:08:00 +0100

Add Templates Folder, Union Find

- format.sh
  * Fix detection for modified files
  * Format templates

Diffstat:
M
README.md
 | 
4
++++
A
Templates/Union_Find.cpp
 | 
27
+++++++++++++++++++++++++++
M
format.sh
 | 
2
+-

3 files changed, 32 insertions(+), 1 deletion(-)
diff --git a/README.md b/README.md
@@ -266,6 +266,10 @@ if you have any questions.
 |  2477  |   Medium   | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp)                                  |
 |  2492  |   Medium   | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp)                                  |
 
+## Templates
+
+* [Union Find](Templates/Union_Find.cpp)
+
 ## DNF
 
 | Number | Difficulty | Solution                                                                                        |
diff --git a/Templates/Union_Find.cpp b/Templates/Union_Find.cpp
@@ -0,0 +1,27 @@
+class UnionFind {
+  int n;
+  vector<int> root, rank;
+
+public:
+  UnionFind(int n) : n(n), root(n), rank(n, 1) {
+    iota(root.begin(), root.end(), 0);
+  }
+
+  int find(int x) {
+    while (x != root[x]) x = root[x] = root[root[x]];
+    return x;
+  }
+
+  void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+      if (rank[x] > rank[y]) swap(x, y);
+      root[x] = y;
+      rank[y] += 1;
+      n--;
+    }
+  }
+
+  int count() { return n; }
+  bool connected(int x, int y) { return find(x) == find(y); }
+};
diff --git a/format.sh b/format.sh
@@ -1,7 +1,7 @@
 #!/bin/bash
 # Format newly added files using clang-format
 
-for i in $(git status | grep Problems | xargs)
+for i in $(git status | grep -Eo "(Problems|Templates).*")
 do
   echo "Formating: $i"
   clang-format -i $i