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.

```
/*
```

* C++ Program to Implement Disjoint Set Data Structure

```
 */
```
```
#include <iostream>
```
```
#include <cstdio>
```
```
#include <vector>
```
```
#include <algorithm>
```
```
using namespace std;
```
```
#define INF 1000000000
```
```
 
```
```
typedef pair<int ,int> ii;
```
```
typedef vector <int> vi;
```
```
 
```
```
vector <pair<int ,ii> > edges;
```
```
vi pset;
```
```
 
```
```
void init(int N)
```
```
{
```
```
    pset.assign(N, 0);
```
```
    for(int i = 0; i < N; i++)
```
```
    {
```
```
        pset[i] = i;
```
```
    }
```
```
}
```
```
 
```
```
int find_set(int i)
```
```
{
```
```
    if(pset[i] == i)
```
```
    {
```
```
        return pset[i];
```
```
    }
```
```
    return pset[i] = find_set(pset[i]);
```
```
}
```
```
bool issameset (int i, int j)
```
```
{
```
```
    return find_set(i) == find_set(j);
```
```
}
```
```
void joinset(int i, int j)
```
```
{
```
```
    pset[find_set(i)] = find_set(j);
```
```
}
```
```
int main()
```
```
{
```
```
    int n, m, a, b, dist, t;
```
```
    cin>>t;
```
```
    while(t--)
```
```
    {
```
```
        cin>>n>>m;
```
```
        init(n);
```
```
        edges.clear();
```
```
        for (int i = 0; i < m; i++)
```
```
        {
```
```
            cin>>a>>b>>dist;
```
```
            a--,b--;
```
```
            ii tmp = make_pair(a, b);
```

            edges.push_back(make_pair(dist, tmp));

```
        }
```

        sort(edges.rbegin(),edges.rend());

```
        int sum = 0;
```

        for(int i = 0; i < edges.size(); i++)

```
        {
```

            if (!issameset (edges[i].second.first, edges[i].second.second))

```
            {
```

               joinset(edges[i].second.first, edges[i].second.second);

```
            }
```
```
            else sum += edges[i].first;
```
```
        }
```
```
        cout<<sum;
```
```
    }
```
```
    cin>>t;
```
```
    getch();
```
```
}
```

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.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Pagoda

» Next - C++ Program to Check if a Binary Tree is BST or Not

Related Posts:

Recommended Articles: