union find und Segementbaum

1 files changed, 19 insertions, 0 deletions

diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
new file mode 100644
index 0000000..19513ab
--- /dev/null
+++ b/datastructures/unionFind.cpp
@@ -0,0 +1,19 @@
+vector<int> parent, rank2; //mache compiler verbieten Variable mit Namen rank
+
+int findSet(int n) { //Pfadkompression
+	if (parent[n] != n) parent[n] = findSet(parent[n]);
+	return parent[n];
+}
+
+void linkSets(int a, int b) { //union by rank
+	if (rank2[a] < rank2[b]) parent[a] = b;
+	else if (rank2[b] < rank2[a]) parent[b] = a;
+	else {
+		parent[a] = b;
+		rank2[b]++;
+	}
+}
+
+void unionSets(int a, int b) {
+	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
+}
\ No newline at end of file