Union Find Algorithm(dis-joint set data structure) and related UVA problems.

[Atiqur Rahman]

The problem was to make set of some related elements. Operations that
might be needed are:
* Query an element to which set it belongs.
* How many elements are in a group or set
* How many maximum sets/groups exist


A first thought solution
=====================
An first time solution might be using 2D array or array of vectors
like adjacency lists. Adding every related elements to one's adjacency
list. This will work. But in case when number elements are in great
range this is not efficient.

Dis-joint set data structure for Union find Algorithm
==========================================
I designed the following functions:

A function to initialize the set.

void makeSet(int n) {

// Initialization
int i;

for (i=1; i<=n; i++) {

sets[i] = i;
rank[i] = 0;
no_child[i] = 1;
}

}



Another function to return root of an element (useful to determine in
which set an element belongs)

int findSet(int i) {

if (sets[i] == i)
return i;
else
return findSet(sets[i]);

}



Adding two related elements to same set.

void Union(int x, int y) {
Link(findSet(x), findSet(y));
}

Linking elements
void Link(int x, int y) {
if (x != y) {
if (rank[x]>rank[y]) {
sets[y] = x;
no_child[x] += no_child[y];
}
else {
sets[x] = y;
no_child[y] += no_child[x];
if (rank[x]==rank[y])
rank[y]++;
}
}
}


Running Time:
=============
Running time is O(m log n)
m is number of pairs to Union and n is total number of elements

Related UVA problems:
======================
If you solve 10608 you will be able to solve 10583 and 10685 with
simple modifications. I am providing no special case. I don't think if
there are any.

References:
===========
Introduction to Algorithms (Thomas H Cormen ..) page 505.

[Atiqur Rahman]

Also tell me if you find problems on this algorithm.
Thanks.