Is the Union-Find (or Disjoint Set) data structure in STL?

Question

I would have expected such a useful data structure to be included in the C++ Standard Library but I can't seem to find it.

Answer 1

It is not, but there is one in boost: http://www.boost.org/doc/libs/1_64_0/libs/disjoint_sets/disjoint_sets.html, so if you want an off-the-shelf implementation I'd recommend this.

Answer 2

No. I written a simple implementation. It's very extensible.

struct DisjointSet {
    vector<int> parent;
    vector<int> size;

    DisjointSet(int maxSize) {
        parent.resize(maxSize);
        size.resize(maxSize);
        for (int i = 0; i < maxSize; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

And the usage as follows.

void solve() {
    int n;
    cin >> n;
    DisjointSet S(n);  // Initializing with maximum Size
    S.union_set(1, 2);
    S.union_set(3, 7);
    int parent = S.find_set(1);  // root of 1
}

Answer 3

The implementation of disjoint set using tree. There are two operations:

1. find_set(x): get representative of set which contains member x, here representative is the root node
2. union_set(x,y): union of two sets which contain members x and y

Tree representation is efficient than linked list representation with two heuristics: -- "union by rank" and "path compression" --

union by rank: assign rank to each node. Rank is height of the node (number of edges in the longest simple path between the node and a descendant leaf)

path compression: during "find_set" operation, make parent of node as root

(Ref: Introduction to Algorithms, 3rd Edition by CLRS)

The STL implementation is given below:

#include <iostream>
#include <vector>
using namespace std;

struct disjointSet{
    vector<int> parent, rank;
    disjointSet(int n){
        rank.assign(n, 0);
        for (int i = 0; i < n; i++)
            parent.push_back(i);
    }

    int find_set(int v){
        if(parent[v]!=v)
            parent[v] = find_set(parent[v]);
        return parent[v];
    }

    void union_set(int x,int y){
        x = find_set(x);
        y = find_set(y);
        if (rank[x] > rank[y])
            parent[y] = x;
        else{
            parent[x] = y;
            if(rank[x]==rank[y])
                rank[y]++;
        }
    }
};