STANAANDREY

kruskal cls

Mar 15th, 2021 (edited)
406
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. #define NMAX 103
  4. struct {
  5.     int x, y;
  6.     float cost;
  7. } edge[NMAX];
  8. int n, m, subArbOf[NMAX * NMAX];
  9. float sum;
  10.  
  11. void read() {
  12.     cin >> n >> m;
  13.     for (int i = 1; i <= m; i++) {
  14.         cin >> edge[i].x >> edge[i].y >> edge[i].cost;
  15.     }
  16. }
  17.  
  18. void bubbleSort() {
  19.     bool sorted = false;
  20.     while (!sorted) {
  21.         sorted = true;
  22.         for (int i = 1; i < m; i++) {
  23.             if (edge[i].cost > edge[i + 1].cost) {
  24.                 swap(edge[i], edge[i + 1]);
  25.                 sorted = false;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. void kruskal() {
  32.     for (int i = 1; i <= n; i++) {
  33.         subArbOf[i] = i;
  34.     }
  35.     for (int i = 1; i <= m; i++) {
  36.         if (subArbOf[edge[i].x] != subArbOf[edge[i].y]) {
  37.             sum += edge[i].cost;
  38.  
  39.             int subArbOfX = subArbOf[edge[i].x],
  40.                 subArbOfY = subArbOf[edge[i].y];
  41.             for (int j = 1; j <= n; j++) {
  42.                 if (subArbOf[j] == subArbOfY) {
  43.                     subArbOf[j] = subArbOfX;
  44.                 }
  45.             }
  46.         }
  47.     }
  48. }
  49.  
  50. int main() {
  51.     read();
  52.     bubbleSort();
  53.     kruskal();
  54.     cout << sum << endl;
  55.     return 0;
  56. }
  57.  
Add Comment
Please, Sign In to add comment