Algorithms : complete 03-algorithms_on_graphs 05-minimum_spanning_tree

2 files changed, 192 insertions, 19 deletions

diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp
index f8b58af..7cf3bef 100644
--- a/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/01-connecting_points/connecting_points.cpp
@@ -6,18 +6,104 @@
 
 using std::vector;
 
-double minimum_distance(vector<int> x, vector<int> y) {
-  double result = 0.;
-  //write your code here
-  return result;
-} 
+struct Vertex
+{
+    int a;
+    int b;
+    double l;
+
+    static int compare(Vertex &a, Vertex &b)
+    {
+        return (a.l < b.l);
+    }
+
+    void print()
+    {
+        std::cout << a << ";" << b << " " << l << std::endl;
+    }
+};
+
+struct Point
+{
+    int x;
+    int y;
+    int parent;
+
+    void print()
+    {
+        std::cout << x << ";" << y << " " << parent << std::endl;
+    }
+};
+
+struct Points
+{
+    vector<Point> points;
+    vector<Vertex> vertices;
+
+    Points(int n) : points(n), vertices(n*n) { }
+
+    void read(int i)
+    {
+        std::cin >> points[i].x >> points[i].y;
+        points[i].parent = i;
+    }
+
+    void print()
+    {
+        for (int i = 0; i < points.size(); i++)
+            points[i].print();
+    }
+
+    int find(int i)
+    {
+        if (points[i].parent == i)
+            return i;
+        points[i].parent = find(points[i].parent);
+        return points[i].parent;
+    }
+
+    double solve()
+    {
+        int x = 0;
+        for (int i = 0; i < points.size(); i++) {
+            for (int j = i + 1; j < points.size(); j++) {
+                vertices[x].a = i;
+                vertices[x].b = j;
+                vertices[x].l =  sqrt(
+                        (points[i].x - points[j].x) * (points[i].x - points[j].x)
+                        +
+                        (points[i].y - points[j].y) * (points[i].y - points[j].y)
+                        );
+                x += 1;
+            }
+        }
+        vertices.resize(x);
+
+        std::sort(vertices.begin(), vertices.end(), Vertex::compare);
+
+        int n = 0;
+        double result = 0.;
+        for (int i = 0; i < vertices.size(); i++) {
+            int realA = find(vertices[i].a);
+            int realB = find(vertices[i].b);
+            if (realA != realB) {
+                result += vertices[i].l;
+                n += 1;
+                if (n == points.size())
+                    break;
+                points[realB].parent = realA;
+            }
+        }
+
+        return result;
+    }
+};
 
 int main() {
   size_t n;
   std::cin >> n;
-  vector<int> x(n), y(n);
-  for (size_t i = 0; i < n; i++) {
-    std::cin >> x[i] >> y[i];
-  }
-  std::cout << std::setprecision(10) << minimum_distance(x, y) << std::endl;
+  Points points(n);
+  for (size_t i = 0; i < n; i++)
+      points.read(i);
+  std::cout << std::setprecision(10) << points.solve() << std::endl;
 }
diff --git a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp
index 31f00e1..167dc5c 100644
--- a/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp
+++ b/03-algorithms_on_graphs/05-minimum_spanning_tree/02-clustering/clustering.cpp
@@ -9,20 +9,107 @@ using std::vector;
 using std::pair;
 
 
+struct Vertex
+{
+    int a;
+    int b;
+    double l;
 
-double clustering(vector<int> x, vector<int> y, int k) {
-  //write your code here
-  return -1.;
-} 
+    static int compare(Vertex &a, Vertex &b)
+    {
+        return (a.l < b.l);
+    }
+
+    void print()
+    {
+        std::cout << a << ";" << b << " " << l << std::endl;
+    }
+};
+
+struct Point
+{
+    int x;
+    int y;
+    int parent;
+
+    void print()
+    {
+        std::cout << x << ";" << y << " " << parent << std::endl;
+    }
+};
+
+struct Points
+{
+    vector<Point> points;
+    vector<Vertex> vertices;
+
+    Points(int n) : points(n), vertices(n*n) { }
+
+    void read(int i)
+    {
+        std::cin >> points[i].x >> points[i].y;
+        points[i].parent = i;
+    }
+
+    void print()
+    {
+        for (int i = 0; i < points.size(); i++)
+            points[i].print();
+    }
+
+    int find(int i)
+    {
+        if (points[i].parent == i)
+            return i;
+        points[i].parent = find(points[i].parent);
+        return points[i].parent;
+    }
+
+    double solve(int k)
+    {
+        int x = 0;
+        for (int i = 0; i < points.size(); i++) {
+            for (int j = i + 1; j < points.size(); j++) {
+                vertices[x].a = i;
+                vertices[x].b = j;
+                vertices[x].l =  sqrt(
+                        (points[i].x - points[j].x) * (points[i].x - points[j].x)
+                        +
+                        (points[i].y - points[j].y) * (points[i].y - points[j].y)
+                        );
+                x += 1;
+            }
+        }
+        vertices.resize(x);
+
+        std::sort(vertices.begin(), vertices.end(), Vertex::compare);
+
+        int n = 0;
+        double result = 0.;
+        for (int i = 0; i < vertices.size(); i++) {
+            int realA = find(vertices[i].a);
+            int realB = find(vertices[i].b);
+            if (realA != realB) {
+                if (n == points.size() - k) {
+                    result = vertices[i].l;
+                    break;
+                }
+                n += 1;
+                points[realB].parent = realA;
+            }
+        }
+
+        return result;
+    }
+};
 
 int main() {
   size_t n;
   int k;
   std::cin >> n;
-  vector<int> x(n), y(n);
-  for (size_t i = 0; i < n; i++) {
-    std::cin >> x[i] >> y[i];
-  }
+  Points points(n);
+  for (size_t i = 0; i < n; i++)
+      points.read(i);
   std::cin >> k;
-  std::cout << std::setprecision(10) << clustering(x, y, k) << std::endl;
+  std::cout << std::setprecision(10) << points.solve(k) << std::endl;
 }