connected_components.c

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

struct node {
  int rank;
  char data;
  struct node* parent;
};

struct node* create_node(char data);
struct node* FindSet(struct node* node);
void Union(struct node* node_1, struct node* node_2);
int char_to_idx(char c) { return c - 'a'; }
int idx_to_char(int i) { return 'a' + i; }

int main(void) {
  int vertices = 0, // Number of vertices
    edges = 0, // Number of edges
    test_cases, // Number of test cases
    i, j, k; // Counters
  char v1, v2; // Vertices labels read from stdin

  scanf(" %d\n", &test_cases);

  struct node* disjoint_set[26];

  for (i = 0; i < test_cases; i++) {
    scanf("%d %d\n", &vertices, &edges);

    char c;
    for (c = 'a'; c < 'a' + vertices; c++) {
      disjoint_set[c - 'a'] = create_node(c);
    }

    for (j = 0; j < edges; j++) {
      scanf("%c %c\n", &v1, &v2);
      if (v1 == v2) continue;
      Union(disjoint_set[char_to_idx(v1)], disjoint_set[char_to_idx(v2)]);
    }

    printf("Case #%d:\n", i + 1);
    int roots = 0;
    for (j = 0; j < vertices; j++) {
      if (FindSet(disjoint_set[j]) == disjoint_set[j]) {
        for (k = 0; k < vertices; k++) {
          if (FindSet(disjoint_set[k]) == disjoint_set[j]) {
            printf("%c,", disjoint_set[k]->data);
          }
        }
        printf("\n");
        roots++;
      }
    }

    for (j = 0; j < vertices; j++) free(disjoint_set[j]);

    printf("%d connected components%s", roots, i+1 < test_cases ? "\n\n" : "\n");
  }
  return 0;
}

struct node* create_node(char data) {
  struct node* new_node = malloc(sizeof(struct node));

  new_node->rank = 0;
  new_node->data = data;
  new_node->parent = new_node;

  return new_node;
}

struct node* FindSet(struct node* node) {
  if (node->parent == node) return node;

  node->parent = FindSet(node->parent);

  return node->parent;
}

void Union(struct node* node_1, struct node* node_2) {
  struct node* set_1 = FindSet(node_1);
  struct node* set_2 = FindSet(node_2);

  if (set_1 == set_2) return;

  if (set_1->rank > set_2->rank)
    set_2->parent = set_1;
  else if (set_1->rank < set_2->rank)
    set_1->parent = set_2;
  else {  // Equal ranks
    set_2->parent = set_1;
    set_1->rank++;
  }
}