Counting number of members in a disjoint set

Question

I am having a little bit of trouble counting the number of elements in each of my disjoint set members. For example, if someone enters in:

Note: first number = source vertex, 2nd number = destination vertex, 3rd number = length

0 2 1

4 8 7

5 8 6

1 2 5

2 3 17

I would have 2 as a count for the set

4 8 7

5 8 6

and 3 as a count for the set as both are connected by 2 and 3 (respective) elements.

0 2 1

1 2 5

2 3 17

I had the idea of storing the count of the number of elements for each disjoint set, into an integer array, so I can access the count for ever disjoint set. Below are my implementations for finding elements and unioning them into the same set. I also have a function for finding the root in every set.

int node::findSet(int v, int *parent)
{
  if(parent[v] < 0)
    return v;
  else
  {
    return parent[v] = findSet(parent[v], parent);
  }
}

void node::joinSets(int c, int p1, int p2, int *parents)
{
  join(findSet(p1,parents),findSet(p2,parents),parents);
}

void node::join(int p1, int p2, int *parents)
{
  if(parents[p2] < parents[p1])
    parents[p1] = p2;
  else
  {
    if(parents[p1] == parents[p2])
      parents[p1]--;
    parents[p2] = p1;
  }
}

I'm just not sure where/when to increment and maintain my counter. Any help would be appreciated. Thanks!

Answer 1

If you want to count the number of edges connecting each disjoint set, store the current size of every root in an array similar to parents.

When an edge comes, find roots of both nodes. If they're equal, increment the counter for the root (I'm assuming there are no repeating edges). If they're not, union the roots, and for the resultant root's counter value put the sum of the roots' counter values plus one.