// Este arquivo: UF.c
// Data: 2019-07-17
// Digitador: Paulo Feofiloff
//
// Esta é uma implementação de uma estrutura Union-Find especializada para
// vértices de grafos (veja GRAPHlists.h e GRAPHlists.c). O código inclui os
// truques "path compression" e "union-by-rank".
//
// O código é uma adaptação dos programas do livro "Algorithms", 3rd.ed.,
// part 1, de Sedgewick.
////////////////////////////////////////////////////////////////////////////////


#include "UF.h"
// inclui MYTOOLS.h e a definição de vértice (#define vertex int)

// Estrutura de dados privada.
static vertex *chefe;
static int *size;

void 
UFinit( int V) {
   chefe = mallocc( V * sizeof (vertex)); 
   size = mallocc( V * sizeof (int)); 
   for (vertex v = 0; v < V; ++v) { 
      chefe[v] = v; 
      size[v] = 1; 
   }
}

vertex 
UFfind( vertex v) { 
   vertex v0 = v; 
   while (v0 != chefe[v0]) 
      v0 = chefe[v0]; // path compression
   return v0; 
}

void
UFunion( vertex v0, vertex w0) { 
   if (size[v0] < size[w0]) { // union-by-rank
      chefe[v0] = w0; 
      size[w0] += size[v0]; 
   }
   else { 
      chefe[w0] = v0; 
      size[v0] += size[w0]; 
   }
}

void 
UFfree( void) { 
   free( chefe);
   free( size);
}

////////////////////////////////////////////////////////////////////////////////