Self-referential struct in c++ for union-find

72 views Asked by At

The following is a Java implementation of union-find, and I wish to replicate the same in C++:


class v_rank{
    int position, rank;
    v_rank parent;
    public v_rank(int position){
        this.position = position;
        rank = 0;
        parent = null;
    }
}
static v_rank find(v_rank v){
    if(v.parent == null)
        return v;
    v.parent = find(v.parent);
    return v.parent;
}

static void union(v_rank root1, v_rank root2){
    if(root1.rank < root2.rank)
        root1.parent = root2;
    else if(root1.rank > root2.rank)
        root2.parent = root1;
    else{
        root2.parent = root1;
        root1.rank++;
    }
}

What I tried for C++:

struct vert {
    int pos, rank;
    vert* par;
    vert(int pos) {
        this->pos = pos;
        rank = 0;
        par =  NULL;
    }
};

vert find(vert v) {
    if (v.par == NULL)
        return v;
    *(v.par) = find(*(v.par));
    return *(v.par);
}

Unlike java with such an implementation I cannot compare 2 vert with a simple '=='. I need to make a pair of 2 such verts and then a vector of all such pair (edges). I'm having issues with that as well.

Can someone suggest a way to replicate java code in cpp, such that I'm able to check for equality of two 'verts' and use a vector of pairs of 'verts'?

0

There are 0 answers