Advertisement
Amimul

Disjoint Set in c

Apr 24th, 2018
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. #define SIZE 100
  4.  
  5. struct edge{
  6.     int u, v;
  7. } E[SIZE];
  8.  
  9. struct disjointset
  10. {
  11.     int parent;
  12.     int size;
  13.     int rank;
  14. } S[SIZE];
  15.  
  16. void get_edge_list(int m)
  17. {
  18.     int x, y;
  19.     for(int i = 0; i< m; i++)
  20.     {
  21.         scanf("%d %d", &x, &y);
  22.         E[i].u = x;
  23.         E[i].v= y;
  24.     }
  25. }
  26.  
  27. void initialize_set(int n)
  28. {
  29.     for(int i = 0; i<n; i++)
  30.     {
  31.         S[i].rank = 0;
  32.         S[i].parent = i;
  33.         S[i].size = 1;
  34.     }
  35. }
  36.  
  37. int find_parent(int u)
  38. {
  39.     if(S[u].parent == u)
  40.     {
  41.         return u;
  42.     }
  43.     else
  44.         return find_parent(S[u].parent);
  45.  
  46. }
  47.  
  48. void unions(int u, int v)
  49. {
  50.     if(S[u].rank > S[v].rank)
  51.     {
  52.         S[v].parent = u;
  53.         S[u].size++;
  54.     }
  55.     else if(S[u].rank < S[v].rank)
  56.     {
  57.         S[u].parent = v;
  58.         S[v].size++;
  59.     }
  60.     else{
  61.         S[v].parent = u;
  62.         S[u].rank ++;
  63.         S[u].size++;
  64.  
  65.     }
  66. }
  67.  
  68. void process_graph(int n, int m)
  69. {
  70.     int u, v;
  71.     initialize_set(n);
  72.     for(int i= 0; i<m; i++)
  73.     {
  74.         u = find_parent(E[i].u);
  75.         v = find_parent(E[i].v);
  76.         if ( u!= v)
  77.             unions(u, v);
  78.     }
  79. }
  80.  
  81. int component_count(int n)
  82. {
  83.     int count = 0;
  84.     for(int i = 0; i< n; i++)
  85.     {
  86.         if(S[i].parent == i)
  87.             count++;
  88.     }
  89.     return count;
  90. }
  91.  
  92. int largest_component_size(int n)
  93. {
  94.     int maz = 0;
  95.     for(int i = 0; i<n; i++)
  96.     {
  97.         if(maz < S[i].size)
  98.             maz = S[i].size;
  99.     }
  100.     return maz;
  101. }
  102.  
  103. void parentNodes(int v)
  104. {
  105.     if(S[v].parent == v)
  106.         return;
  107.     else{
  108.         printf("%d ", S[v].parent);
  109.         return parentNodes(S[v].parent);
  110.     }
  111. }
  112.  
  113. void component_nodes(int n, int v)
  114. {
  115.     for(int i = 0; i<n; i++)
  116.     {
  117.         if(S[v].parent == S[i].parent)
  118.         {
  119.             printf("%d ", i);
  120.         }
  121.     }
  122. }
  123.  
  124.  
  125. int main()
  126. {
  127.     freopen("input.txt", "r", stdin);
  128.     int n,m;
  129.     scanf("%d %d", &n, &m);
  130.     get_edge_list(m);
  131.     process_graph(n, m);
  132.     for(int i = 0; i< n; i++)
  133.     {
  134.         printf("%d have rank %d and parent %d and size %d\n", i, S[i].rank, S[i].parent, S[i].size);
  135.     }
  136.     printf("Total component %d\n", component_count(n));
  137.     printf("Largest component size is %d\n", largest_component_size(n));
  138.     parentNodes(2);
  139.     printf("\n");
  140.     component_nodes(n, 3);
  141.     return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement