Union Find

union_find.c

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

#define EXIT_SUCCESS  0
#define EXIT_FAILURE  1

typedef enum { false=0, true } bool;

typedef struct _uf_node {
  int data;
  int weight;
  int index;
  struct _uf_node *parent;
} UFNode;

typedef struct _union_find {
  int components;
  int size;
  UFNode *nodes;
} UnionFind;

int initUF(UnionFind *uf, int size) {
  int i;
  void *aux;
  UFNode *aux_node;
  aux = malloc(sizeof(UFNode)*size);
  if (aux == NULL) return EXIT_FAILURE;
  uf->nodes = (UFNode *) aux;
  for (i = 0; i < size; ++i) {
    aux_node = uf->nodes+i;
    aux_node->weight = 1;
    aux_node->index = i;
    aux_node->parent = aux_node;
    aux_node->data = 0;
  }
  uf->components = size;
  uf->size = size;
  return EXIT_SUCCESS;
}

void clearUF(UnionFind *U) {
  free(U->nodes);
  U->nodes = NULL;
  U->size = 0;
  U->components = 0;
}

UFNode *qfind(UnionFind *U, int index) {
  UFNode *curr;
  UFNode *tmp;
  UFNode *root;
  curr = U->nodes+index;
  while (curr->parent != curr) {
    curr = curr->parent;
  }
  root = curr;
  curr = U->nodes+index;
  while (curr->parent != curr) {
    tmp = curr->parent;
    curr->parent = root;
    curr = tmp;
  }
  return root;
}

UFNode *nfind(UnionFind *U, int index) {
  UFNode *curr;
  UFNode *tmp;
  UFNode *root;
  curr = U->nodes+index;
  while (curr->parent != curr) {
    curr = curr->parent;
  }
  root = curr;
  return root;
}

bool connected(UnionFind *U, int p, int q) {
  if ((p < 0 || p >= U->size) ||
    (q < 0 || q >= U->size))
    return false;
  if (p == q) return true;
  UFNode *p_root = qfind(U, p);
  UFNode *q_root = qfind(U, q);
  if (p_root == q_root)
    return true;
  else
    return false;
}

int get_size(UnionFind *U) {
  return U->size;
}

int get_components(UnionFind *U) {
  return U->components;
}

void show_nodes(UnionFind *U) {
  int i;
  if (U->size > 0) {
    printf("%d", U->nodes[0].parent->index);
    for (i = 1; i < U->size; i++) {
      printf(" %d", U->nodes[i].parent->index);
    }
    printf(" (");
    printf("%d", nfind(U, 0)->index);
    for (i = 1; i < U->size; i++) {
      printf(" %d", nfind(U, i)->index);
    }
    printf(" )");
    printf("\n");
  }
}

bool qunion(UnionFind *U, int p, int q) {
  if ((p < 0 || p >= U->size) ||
    (q < 0 || q >= U->size))
    return false;
  if (p == q) return true;
  UFNode *p_root = qfind(U, p);
  UFNode *q_root = qfind(U, q);
  if (p_root->weight > q_root->weight) {
    q_root->parent = p_root;
    p_root->weight += q_root->weight;
  } else {
    p_root->parent = q_root;
    q_root->weight += p_root->weight;
  }
  U->components--;
  return true;
}

int main(int argc, char **argv) {
  UnionFind U;
  int m;
  int p, q, i;
  initUF(&U, 10);
  printf("Cantidad de nodos: %d\n", get_size(&U));
  show_nodes(&U);
  scanf("%d\n", &m);
  for (i = 0; i < m; i++) {
    scanf("%d %d\n", &p, &q);
    qunion(&U, p, q);
  }
  show_nodes(&U);
  clearUF(&U);
  return 0;
}