#include <stdio.h>
#include <stdlib.h>

#define N (200)

int *id,*sz;
int n;

void uf3(int numElements)
{
int i;

n=numElements;
id=(int*) malloc(n*sizeof(int));
sz=(int*) malloc(n*sizeof(int));
if (!id || !sz)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}

for (i=0; i<n; i++)
{
  id[i]=i;
  sz[i]=1;
}
}

int find(int x)
// Find root of tree containing x
{
int i,j,root;

// Find root
for (i=x;
     id[i]!=i;
     i=id[i])
  ;
root=i;
// path compression - make all nodes on path
// point directly at the root
for (i=x;
     id[i]!=i;
     j=id[i],id[i]=root,i=j)
  ;
return root;
}

void unionFunc(int i,int j)
{
if (sz[i]<sz[j])
{
  id[i]=j;
  sz[j]+=sz[i];
}
else
{
  id[j]=i;
  sz[i]+=sz[j];
}
}

int main()
{
int i,j,iLeader,jLeader;

int counter=0,numTrees=N;

srandom(666);
uf3(N);
while (numTrees>1)
{
  counter++;
  i=labs(random())%200;
  j=labs(random())%200;
  iLeader=find(i);
  jLeader=find(j);
  if (iLeader!=jLeader)
  {
    printf("%d %d: find(%d)=%d find(%d)=%d\n",
      numTrees,counter,i,iLeader,j,jLeader);
    unionFunc(iLeader,jLeader);
    numTrees--;
    counter=0;
  }
}

free(id);
free(sz);
}