make union find a struct, remove kruskal

5 files changed, 46 insertions, 43 deletions

diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index c4bd312..1c51475 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -123,11 +123,12 @@
 
 \begin{algorithm}{Union-Find}
 	\begin{methods}
-		\method{init}{legt $n$ einzelne Unions an}{n}
-		\method{findSet}{findet den Repräsentanten}{\log(n)}
-		\method{unionSets}{vereint 2 Mengen}{\log(n)}
+		\method{UnionFind}{legt $n$ einzelne Elemente an}{n}
+		\method{find}{findet den Repräsentanten}{\log(n)}
+		\method{link}{vereint 2 Mengen}{\log(n)}
 		\method{size}{zählt Elemente in Menge, die $a$ enthält}{\log(n)}
-		\method{m\*findSet + n\*unionSets}{Folge von Befehlen}{n+m\*\alpha(n)}
+		\method{add}{fügt neues einzelnes Element ein}{1}
+		\method{m\*find + n\*link}{Folge von Befehlen}{n+m\*\alpha(n)}
 	\end{methods}
 	\sourcecode{datastructures/unionFind.cpp}
 \end{algorithm}
diff --git a/content/datastructures/unionFind.cpp b/content/datastructures/unionFind.cpp
index dd5a569..36a4b45 100644
--- a/content/datastructures/unionFind.cpp
+++ b/content/datastructures/unionFind.cpp
@@ -1,26 +1,26 @@
-// unions[i] >= 0 => unions[i] =  parent
-// unions[i]  < 0 => unions[i] = -size
-vector<int> unions;
+struct UnionFind {
+	vector<int> unions; // unions[i] = parent or unions[i] = -size
 
-void init(int n) { //Initialisieren
-	unions.assign(n, -1);
-}
+	UnionFind(int n): unions(n, -1) {}
 
-int findSet(int a) { // Pfadkompression
-	if (unions[a] < 0) return a;
-	return unions[a] = findSet(unions[a]);
-}
+	int find(int a) {
+		return unions[a] < 0 ? a : unions[a] = find(unions[a]);
+	}
 
-void linkSets(int a, int b) { // Union by size.
-	if (unions[b] > unions[a]) swap(a, b);
-	unions[b] += unions[a];
-	unions[a] = b;
-}
+	bool link(int a, int b) {
+		if ((a = find(a)) == (b = find(b))) return false;
+		if (unions[b] > unions[a]) swap(a, b);
+		unions[b] += unions[a];
+		unions[a] = b;
+		return true;
+	}
 
-void unionSets(int a, int b) { // Diese Funktion aufrufen.
-	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
-}
+	int size(int a) {
+		return -unions[find(a)];
+	}
 
-int size(int a) {
-	return -unions[findSet(a)];
-}
+	int add() {
+		unions.push_back(-1);
+		return ssize(unions) - 1;
+	}
+};
diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp
index deac71e..b7545d5 100644
--- a/content/graph/cycleCounting.cpp
+++ b/content/graph/cycleCounting.cpp
@@ -38,13 +38,11 @@ struct cycles {
 
 	bool isCycle(cycle cur) {// cycle must be constructed from base
 		if (cur.none()) return false;
-		init(ssize(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@
+		UnionFind uf(ssize(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@
 		for (int i = 0; i < ssize(edges); i++) {
 			if (cur[i]) {
 				cur[i] = false;
-				if (findSet(edges[i].first) ==
-				    findSet(edges[i].second)) break;
-				unionSets(edges[i].first, edges[i].second);
+				if (!uf.link(edges[i].first, edges[i].second)) break;
 		}}
 		return cur.none();
 	}
diff --git a/content/graph/graph.tex b/content/graph/graph.tex
index e46ad07..bf51d74 100644
--- a/content/graph/graph.tex
+++ b/content/graph/graph.tex
@@ -10,11 +10,13 @@
 	Für jeden Kreis $K$ im Graphen gilt:
 	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
 
-	\subsection{\textsc{Kruskal}}
-	\begin{methods}[ll]
-		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
-	\end{methods}
-	\sourcecode{graph/kruskal.cpp}
+	\optional{
+		\subsubsection{\textsc{Kruskal}'s Algorithm \opthint}
+		\begin{methods}[ll]
+			berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+		\end{methods}
+		\sourcecode{graph/kruskal.cpp}
+	}
 \end{algorithm}
 
 \begin{algorithm}{Heavy-Light Decomposition}
diff --git a/content/graph/kruskal.cpp b/content/graph/kruskal.cpp
index d42800d..98a2682 100644
--- a/content/graph/kruskal.cpp
+++ b/content/graph/kruskal.cpp
@@ -1,9 +1,11 @@
-ranges::sort(edges, less{});
-vector<Edge> mst;
-ll cost = 0;
-for (Edge& e : edges) {
-	if (findSet(e.from) != findSet(e.to)) {
-		unionSets(e.from, e.to);
-		mst.push_back(e);
-		cost += e.cost;
-}}
+ll kruskal(int n, vector<Edge> edges, vector<Edge> &mst) {
+	ranges::sort(edges, less{});
+	ll cost = 0;
+	UnionFind uf(n); // union find @\sourceref{datastructures/unionFind.cpp}@
+	for (Edge &e: edges) {
+		if (uf.link(e.from, e.to)) {
+			mst.push_back(e);
+			cost += e.cost;
+	}}
+	return cost;
+}