Disjoint set as linked list

Question

Can anyone point me to some info on Disjoint sets as linked list? I cant find any code on this. Language C++

Answer 1

I just wrote this, if anyone is still interested. I was implementing CLRS Chap 21.1

/******************************************************************
* PROGRAM: Implementation of Linked-list representation of disjoi-*
*          nted sets in C++ without weighted union optimization.  *
*          makeset, find takes O(1), Union takes O(n). Testing    *
*          code is in the main method.                            * 
* AUTHOR:  Bo Tian (bt288 at cam.ac.uk) drop me an email if you   *
*          have any questions.                                    *
* LICENSE: Creative Commons Attribution 3.0 Unported              *
*          http://creativecommons.org/licenses/by/3.0/            *
*******************************************************************/ 


#include <iostream>
using namespace std;

long NodeAddress[10] = {0};
int n=0;

template<class T> class ListSet {
private:
    struct Item;
    struct node {
        T val;
        node *next;
        Item *itemPtr;
    };
    struct Item {
        node *hd, *tl;
    };

public:
    ListSet() { }
    long makeset(T a);
    long find (long a);
    void Union (long s1, long s2);
};

template<class T> long ListSet<T>::makeset (T a) {
    Item *newSet = new Item;
    newSet->hd = new node;
    newSet->tl = newSet->hd;
    node *shd = newSet->hd;
    NodeAddress[n++] = (long) shd;
    shd->val = a;
    shd->itemPtr = newSet;
    shd->next = 0;
    return (long) newSet;
}

template<class T> long ListSet<T>::find (long a) {
    node *ptr = (node*)a;
    return (long)(ptr->itemPtr);
}

template<class T> void ListSet<T>::Union (long s1, long s2) {
    //change head pointers in Set s2
    Item *set2 = (Item*) s2;
    node *cur = set2->hd;

    Item *set1 = (Item*) s1;

    while (cur != 0) {
        cur->itemPtr = set1;
        cur = cur->next;
    }
    //join the tail of the set to head of the input set
    (set1->tl)->next = set2->hd;
    set1->tl = set2->tl;
    delete set2;
}

int main () {
    ListSet<char> a;
    long s1, s2, s3, s4;
    s1 = a.makeset('a'); 
    s2 = a.makeset('b'); 
    s3 = a.makeset('c'); 
    s4 = a.makeset('d');
    cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl;
    cout<<a.find(NodeAddress[2])<<endl;
    a.Union(s1, s3);
    cout<<a.find(NodeAddress[2])<<endl;
}

Answer 2

Boost has an implementation: http://www.boost.org/doc/libs/1_39_0/libs/disjoint_sets/disjoint_sets.html. Guess this is what you are looking for.

Answer 3

Well I think you can find information in this page of Wikipedia. Of course, that information is written in pseudo-code, but is not difficult to translate it.