Advertisement
Vaskor096

DSU(disjoint set union)

Jan 20th, 2020
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define MX 100
  3. using namespace std;
  4. int parent[MX];
  5. int parent_rank[MX];
  6.  
  7. void makeset(int n)
  8. {
  9. for(int i=0; i<n; i++)
  10. {
  11. parent[i]=i;
  12. parent_rank[i]=0;
  13. }
  14. }
  15. int findparent (int x)
  16. {
  17. if(x!=parent[x])
  18. {
  19. return parent[x]=findparent(parent[x]);
  20.  
  21. }
  22. else
  23. return x;
  24. }
  25.  
  26. void Unionset(int x,int y)
  27. {
  28. int px=findparent(x);
  29. int py=findparent(y);
  30. if(px==py)
  31. {
  32. return ;
  33. }
  34. if(parent_rank[px]>parent_rank[py])
  35. {
  36. parent[py]=px;
  37. }
  38. else if(parent_rank[px]<parent_rank[py])
  39. {
  40. parent[px]=py;
  41. }
  42. else
  43. {
  44. parent[py]=px;
  45. parent_rank[px]++;
  46. }
  47.  
  48.  
  49. }
  50. void printset(int n)
  51. {
  52. for(int i=0; i<n; i++)
  53. {
  54. cout<<"Node "<<i<<"Parent "<<parent[i]<<"Rank "<<parent_rank[i]<<endl;
  55. }
  56. }
  57.  
  58.  
  59. int main()
  60. {
  61. int n;
  62. cin>>n;
  63. makeset(n);
  64. Unionset(0,1);
  65. Unionset(4,2);
  66. Unionset(3,1);
  67. Unionset(0,3);
  68. Unionset(0,4);
  69. printset(n);
  70.  
  71.  
  72.  
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement