Advertisement
apl-mhd

disjoin set sir

Apr 24th, 2018
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1. #include <iostream>
  2. #include<cstdio>
  3. #define MAX_N 101
  4. #define MAX_M 101
  5. #include <vector>
  6. #include <fstream>
  7. #include <map>
  8. using namespace std;
  9. /*
  10. 10 7
  11. 0 1
  12. 0 2
  13. 1 2
  14. 1 3
  15. 4 5
  16. 4 6
  17. 7 8
  18.  
  19.  
  20. */
  21. int n, m;
  22.  
  23. vector<int> roots;
  24.  
  25.  
  26. struct Set{
  27.     int parent, rnk;
  28. };
  29.  
  30. struct Edge{
  31.  
  32.     int u, v;
  33.  
  34. };
  35.  
  36. Set S[MAX_N];
  37. Edge E[MAX_M];
  38.  
  39. void make_set(){
  40.  
  41.     for(int i=0; i<n; i++){
  42.         S[i].parent = i;
  43.         S[i].rnk = 0;
  44.  
  45.     }
  46. }
  47.  
  48. int find_set(int x){
  49.  
  50.     if(S[x].parent !=x)
  51.         return S[x].parent = find_set(S[x].parent);
  52.     return x;
  53. }
  54.  
  55. void link(int u, int v){
  56.  
  57.     if(S[u].rnk > S[v].rnk){
  58.         S[v].parent = u;
  59.  
  60.     }
  61.     else{
  62.         S[v].parent = u;
  63.         if(S[u].rnk == S[v].rnk)
  64.             ++S[u].rnk;
  65.     }
  66. }
  67.  
  68. void ds_union(int x, int y){
  69.     int u = find_set(x);
  70.     int v = find_set(y);
  71.  
  72.     S[x].parent = u;
  73.     S[y].parent = v;
  74.  
  75.  
  76.     if(u != v)
  77.         link(u,v);
  78.  
  79. }
  80.  
  81. void connected_component(){
  82.     make_set();
  83.     for(int i=0; i<m;i++){
  84.         ds_union(E[i].u,E[i].v);
  85.  
  86.     }
  87.  
  88.     for(int i=0; i<n; i++)
  89.         printf(" %d =  %d \n", i, S[i].parent);
  90.  
  91.     printf("\n");
  92.  
  93. }
  94.  
  95. void find_roots(){
  96.  
  97.     for(int i=0; i<n; i++){
  98.         int r = find_set(i);
  99.         int flag =0;
  100.         for(int j=0; j<roots.size(); ++j){
  101.             if(roots[j] == r){
  102.                 flag = 1;
  103.                 break;
  104.             }
  105.  
  106.         }
  107.         if(flag == 0) roots.push_back(r);
  108.  
  109.     }
  110.  
  111.     for(int i=0; i<roots.size(); i++){
  112.  
  113.         printf("%d", roots[i] );
  114.     }
  115.     cout<<"\n";
  116. }
  117.  
  118.  
  119. int main()
  120. {
  121.  
  122.     map<int, int>mp;
  123.     map<int, int>:: iterator it;
  124.  
  125.     mp[1]=1;
  126.     mp[2] = 2;
  127.  
  128.  
  129.     for(it = mp.begin(); it != mp.end(); it++){
  130.  
  131.         cout<<it->first<<" "<<it->second<<endl;
  132.  
  133.     }
  134.  
  135.     freopen("graph.txt", "r", stdin);
  136.  
  137.     scanf("%d%d",&n,&m);
  138.  
  139.     //cout<<n<<m<<endl;
  140.  
  141.     for(int i=0; i<m;i++){
  142.  
  143.         //cout<<i;
  144.         scanf("%d%d",&E[i].u,&E[i].v);
  145.        // printf("%d %d\n", E[i].u, E[i].v);
  146.  
  147.     }
  148.     connected_component();
  149.     find_roots();
  150.     return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement