/* ========================================================================
   Declarações relativas ao tipo cdisj:
   ===================================================================== */

#ifndef CDISJ
#define CDISJ

/* --------------------------------------------------

   A estrutura Node abaixo sera' usada para representar
   um no' da arvore de conjuntos disjuntos.  Como estes
   nos vao estar todos num vetor, indexado por inteiros
   de 0 a totalelems-1 (veja struct colecao mais abaixo),
   o no' de indice i representa o elemento i do universo.

   Os campos significam:

   int pai: e' o indice de seu pai na estrutura.

   int rank: e' o posto, que so' e' utilizado para
   nos que sao raizes de conjuntos; lembre-se de que no
   inicio todos sao raizes.

   int nelems: guarda o numero de elementos neste conjunto;
   de novo, apenas deve ser mantido para raizes; para os
   outros nos nao importa o valor deste campo.

   DICA: use sempre o comando make para compilar seu
   codigo.  Ele contem a importante diretiva -wall
   (warn all = mostre todos os erros e avisos).

   -------------------------------------------------- */

typedef struct node {
  int pai;
  int rank;
  int nelems;
} Node;

/* --------------------------------------------------

   A estrutura Colecao abaixo sera' usada para representar
   uma colecao de conjuntos disjuntos.  Em cada conjunto,
   os elementos sao inteiros no intervalo de 0 a totalelems-1.

   Os campos significam:

   int totalelems: e' o numero total de elementos no universo
   desta colecao.  Este numero so' muda atraves de operacoes
   Makeset.  As outras operacoes nao modificam este valor.

   Node * element: vetor que guarda os Node's de cada
   elemento.  Deve ser alocado em Makeset e liberado em Libera.

   int nsets: guarda o numero corrente de conjuntos na colecao.
   No inicio (logo depois de um Makeset), este numero e'
   igual a totalelements; mas sempre que dois conjuntos sao
   juntados num so' este numero decresce de uma unidade.

   -------------------------------------------------- */

typedef struct colecao {
  int totalelems;
  Node * element;
  int nsets;
} Colecao;

/* --------------------------------------------------

   Para as rotinas abaixo, veja comentarios em cdisj.c

   -------------------------------------------------- */

int  Makeset(Colecao *C, int n);
void Libera(Colecao *C);
int  Find(Colecao *C, int i);
int  NSets(Colecao *C);
int  NElems(Colecao *C, int r);
int  Union(Colecao *C, int r1, int r2);

#endif