Replacing Kruskal code to be compatible with union find implementation.

1 files changed, 9 insertions, 15 deletions

diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp
index 124c8bb..a955632 100644
--- a/graph/kruskal.cpp
+++ b/graph/kruskal.cpp
@@ -1,15 +1,9 @@
-//Takes a Graph g (EdgeList!!!) with N nodes and computes the MST and Cost of it. Runtime: O(|E|*log(|E|))
-//Requires UnionFind-Datastructure!!!
-pair<graph,int> buildMST(int N, graph& g) {
-  UnionFind uf(N);
-  graph mst; int mst_cost = 0; int M = g.size();
-  sort(g.begin(),g.end());
-  for(int i = 0; i < M; i++) {
-    int u = g[i].second.first, v = g[i].second.second;
-    if(uf.findSet(u) != uf.findSet(v)) {
-      mst.push_back(g[i]); mst_cost += g[i].first;
-      uf.unionSets(u,v);
-    }
-  }
-  return make_pair(mst,mst_cost);
-}
+// Union-Find Implementierung von oben. Laufzeit: O(n*log(n))
+sort(edges.begin(), edges.end());
+vector<ii> mst; int cost = 0;
+for (auto &e : edges) {
+  if (findSet(e.from) != findSet(e.to)) {
+    unionSets(e.from, e.to);
+    mst.push_back(ii(e.from, e.to));
+    cost += e.cost;
+}}