How to store each set in a disjoint-set forest?

Question

Trying to code this up myself in Java... I have created a GraphNode class to represent nodes that have a pointer to their parent.

I have also created a DisjointSet class that includes a MakeSet method that creates a GraphNode object and has its parent reference refer to itself.

The question is: how do I then store each node so I can easily access it later in Union and FindSet? My first thought it to store it in a BST, but I'd have to create a custom TreeNode class that stores not only the value, but also the reference to the GraphNode. Is there an easier way?

Answer 1

There is absolutely an easier way: forget about all the node-business. The nodes are just conceptual, it's not required to implement them literally, and it's easier not to.

All you need is two arrays of ints. One that stores the parents and one that stores the ranks. So in a sort of pseudo-code, it would look something like this:

disjoint_set {
    int[] parent, rank;
    makeset(int n)
    {
        rank = new int[n];
        parent = new int[n];
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int i)
    {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void union(int x, int y)
    {
        x_root = find(x);
        y_root = find(y);
        if (x_root != y_root) {
            if (rank[x_root] < rank[y_root])
                parent[x_root] = y_root;
            else if (rank[x_root] > rank[y_root])
                parent[y_root] = x_root;
            else {
                parent[y_root] = x_root;
                rank[x_root]++;
            }
        }
    }
}