Rkhamim

Untitled

Oct 19th, 2020
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1e4 + 5;
  4. int id[MAX], nodes, edges;
  5. pair <long long, pair<int, int> > p[MAX];
  6.  
  7. void initialize()
  8. {
  9. for(int i = 0;i < MAX;++i)
  10. id[i] = i;
  11. }
  12.  
  13. int root(int x)
  14. {
  15. while(id[x] != x)
  16. {
  17. id[x] = id[id[x]];
  18. x = id[x];
  19. }
  20. return x;
  21. }
  22.  
  23. void union1(int x, int y)
  24. {
  25. int p = root(x);
  26. int q = root(y);
  27. id[p] = id[q];
  28. }
  29.  
  30. long long kruskal(pair<long long, pair<int, int> > p[])
  31. {
  32. int x, y;
  33. long long cost, minimumCost = 0;
  34. for(int i = 0;i < edges;++i)
  35. {
  36. // Selecting edges one by one in increasing order from the beginning
  37. x = p[i].second.first;
  38. y = p[i].second.second;
  39. cost = p[i].first;
  40. // Check if the selected edge is creating a cycle or not
  41. if(root(x) != root(y))
  42. {
  43. minimumCost += cost;
  44. union1(x, y);
  45. }
  46. }
  47. return minimumCost;
  48. }
  49.  
  50. int main()
  51. {
  52. int x, y;
  53. long long weight, cost, minimumCost;
  54. initialize();
  55. cin >> nodes >> edges;
  56. for(int i = 0;i < edges;++i)
  57. {
  58. cin >> x >> y >> weight;
  59. p[i] = make_pair(weight, make_pair(x, y));
  60. }
  61. // Sort the edges in the ascending order
  62. sort(p, p + edges);
  63. minimumCost = kruskal(p);
  64. cout << minimumCost << endl;
  65. return 0;
  66. }
  67.  
Advertisement
Add Comment
Please, Sign In to add comment