Advertisement
apl-mhd

Minimum spanning tree Kruskal

May 7th, 2018
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #include <iostream>
  2. #include<cstdio>
  3. #include <vector>
  4. #include <fstream>
  5. #include <queue>
  6. #include <map>
  7.  
  8. #define MAX_N 101
  9. #define MAX_M 101
  10.  
  11. using namespace std;
  12.  
  13. /*
  14. minimum spanning tree kruskal
  15.  
  16. 6 9
  17. 0 1 1
  18. 0 2 3
  19. 2 1 3
  20. 2 3 1
  21. 1 3 1
  22. 3 5 5
  23. 3 4 4
  24. 4 5 2
  25. 1 5 6
  26. */
  27.  
  28. /*
  29.  Input:
  30.  
  31.        1       6
  32.  (0)------(1)-------(5)
  33.   |      /  |        |
  34.   |     /   |        |
  35. 3 |   3/    | 1      | 2
  36.   |   /     |        |
  37.   |  /      |        |
  38.   | /       |        |
  39.  (2)------(3)------(4)
  40.        1        4
  41.  
  42. */
  43.  
  44.  
  45. /*
  46.  
  47. Output:
  48.  
  49.        1
  50.  (0)------(1)      (5)
  51.            |        |
  52.            |        |
  53.            | 1      |  2
  54.            |        |
  55.            |        |
  56.            |        |
  57.  (2)------(3)------(4)
  58.        1       4
  59.  
  60. */
  61.  
  62.  
  63. int n, m;
  64.  
  65. vector<int> roots;
  66. map<int, int>mp;
  67. map<int, int>:: iterator it;
  68.  
  69.  
  70. struct Set{
  71.     int parent, rnk;
  72. };
  73.  
  74. struct Edge{
  75.  
  76.     int u, v,w;
  77.  
  78.     bool operator<(const Edge& rhs) const {  
  79.  
  80.         return w > rhs.w;
  81.     }
  82.  
  83. };
  84.  
  85. Set S[MAX_N];
  86. Edge E[MAX_M];
  87.  
  88. priority_queue<Edge> q; //for (u,v) minimum weight
  89.  
  90. void make_set(){
  91.  
  92.     for(int i=0; i<n; i++){
  93.         S[i].parent = i;
  94.         S[i].rnk = 0;
  95.  
  96.     }
  97. }
  98.  
  99. int find_set(int x){
  100.  
  101.     if(S[x].parent !=x)
  102.         return S[x].parent = find_set(S[x].parent);
  103.     return x;
  104. }
  105.  
  106.  
  107. void link(int u, int v){
  108.  
  109.     if(S[u].rnk > S[v].rnk){
  110.  
  111.         S[v].parent = u;
  112.     }
  113.     else{
  114.  
  115.         S[u].parent = v;
  116.         if(S[u].rnk ==S[v].rnk)
  117.             S[v].rnk++;
  118.  
  119.     }
  120. }
  121.  
  122.  
  123.  
  124. void ds_union(int x, int y, int w){
  125.     int u = find_set(x);
  126.     int v = find_set(y);
  127.  
  128.    
  129.  
  130.     if(u != v) {
  131.         cout<<"U : "<<x<<", V : "<<y<<", W : "<<w<<endl;
  132.  
  133.         link(u, v);
  134.  
  135.  
  136.     }
  137.  
  138. }
  139.  
  140. void connected_component(){
  141.     make_set();
  142.    
  143.  
  144. cout<<"------printing minimum spanning tree-----\n";
  145.     while(!q.empty()){
  146.  
  147.         Edge temp = q.top();
  148.  
  149.         ds_union(temp.u, temp.v,temp.w);
  150.         q.pop();
  151.  
  152.     }
  153.  
  154. }
  155.  
  156. void find_roots(){
  157.  
  158.     for(int i=0; i<n; i++){
  159.         int r = find_set(i);
  160.         int flag =0;
  161.         for(int j=0; j<roots.size(); ++j){
  162.             if(roots[j] == r){
  163.                 flag = 1;
  164.                 break;
  165.             }
  166.  
  167.         }
  168.         if(flag == 0) roots.push_back(r);
  169.  
  170.     }
  171.  
  172.     for(int i=0; i<roots.size(); i++){
  173.  
  174.         printf("%d", roots[i] );
  175.     }
  176.     cout<<"\n";
  177. }
  178.  
  179.  
  180. int main()
  181. {
  182.  
  183.  
  184.     freopen("graph.txt", "r", stdin);
  185.  
  186.     scanf("%d%d",&n,&m);
  187.  
  188.  
  189.     for(int i=0; i<m;i++){
  190.  
  191.  
  192.         Edge temp;
  193.  
  194.         scanf("%d%d%d",&temp.u, &temp.v, &temp.w);
  195.  
  196.  
  197.         q.push(temp);
  198.  
  199.  
  200.     }
  201.  
  202.     connected_component();
  203.    
  204.     return 0;
  205. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement