C++ Program to Implement Disjoint Set Data Structure

«
»
This C++ program implements the Disjoint Set data structure. It is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets.

Here is the source code of the C++ program to display the sum of data subsets the data strucure has been partitioned in. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

  1. /*
  2. * C++ Program to Implement Disjoint Set Data Structure
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <vector>
  7. #include <algorithm>
  8. using namespace std;
  9. #define INF 1000000000
  10.  
  11. typedef pair<int ,int> ii;
  12. typedef vector <int> vi;
  13.  
  14. vector <pair<int ,ii> > edges;
  15. vi pset;
  16.  
  17. void init(int N)
  18. {
  19.     pset.assign(N, 0);
  20.     for(int i = 0; i < N; i++)
  21.     {
  22.         pset[i] = i;
  23.     }
  24. }
  25.  
  26. int find_set(int i)
  27. {
  28.     if(pset[i] == i)
  29.     {
  30.         return pset[i];
  31.     }
  32.     return pset[i] = find_set(pset[i]);
  33. }
  34. bool issameset (int i, int j)
  35. {
  36.     return find_set(i) == find_set(j);
  37. }
  38. void joinset(int i, int j)
  39. {
  40.     pset[find_set(i)] = find_set(j);
  41. }
  42. int main()
  43. {
  44.     int n, m, a, b, dist, t;
  45.     cin>>t;
  46.     while(t--)
  47.     {
  48.         cin>>n>>m;
  49.         init(n);
  50.         edges.clear();
  51.         for (int i = 0; i < m; i++)
  52.         {
  53.             cin>>a>>b>>dist;
  54.             a--,b--;
  55.             ii tmp = make_pair(a, b);
  56.             edges.push_back(make_pair(dist, tmp));
  57.         }
  58.         sort(edges.rbegin(),edges.rend());
  59.         int sum = 0;
  60.         for(int i = 0; i < edges.size(); i++)
  61.         {
  62.             if (!issameset (edges[i].second.first, edges[i].second.second))
  63.             {
  64.                joinset(edges[i].second.first, edges[i].second.second);
  65.             }
  66.             else sum += edges[i].first;
  67.         }
  68.         cout<<sum;
  69.     }
  70.     cin>>t;
  71.     getch();
  72. }

advertisement
Output
enter the number of sets to be  computed
1
enter the number of disjoint sets and the number of rows
2
3
enter the start and end vertices alongwith weight of edge
1
1
2
enter the start and end vertices alongwith weight of edge
1
1
3
enter the start and end vertices alongwith weight of edge
1
1
4
Sum is:9

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.