Connect cities

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <sys/queue.h>

typedef struct node{
    int city;
    SLIST_ENTRY(node) entry;
} node;

SLIST_HEAD(list, node);

typedef struct super_node{
    list l;
    SLIST_ENTRY(super_node) entry;
} super_node;

SLIST_HEAD(super_list, super_node);

void rec_construct_node(uint32_t n, list *l, list *graph, bool* alreday_seen){
    if (alreday_seen[n]){
        return;
    }
    alreday_seen[n] = true;
    node *el = (node*) malloc(sizeof(node));
    el->city = n;
    SLIST_INSERT_HEAD(l, el, entry);
    node *cur;
    SLIST_FOREACH(cur, &graph[n], entry){
        rec_construct_node(cur->city, l, graph, alreday_seen);
    }
}

super_node *construct_node(uint32_t n, uint32_t nb_node, list *graph, bool* alreday_seen){
    super_node *sn = (super_node*) malloc(sizeof(super_node));
    SLIST_INIT(&(sn->l));
    rec_construct_node(n, &(sn->l), graph, alreday_seen);
    return sn;
}

int main() {
    uint32_t n = 0;
    uint32_t m = 1;
    if (scanf("%d %d", &n, &m) == 0)
        return EXIT_FAILURE;

    list *links = (list *) malloc(n * sizeof(list));
    for (uint32_t i = 0; i < n; i++){
        SLIST_INIT(links + i);
    }


    // graph construction

    uint32_t x, y;
    node *tmp;
    for(uint32_t i = 0; i < m; i++){
        if (scanf("%d %d", &x, &y) == 0)
            return EXIT_FAILURE;
        x--; y--;
        tmp = (node*) malloc(sizeof(node));
        tmp->city = y;
        SLIST_INSERT_HEAD(links + x, tmp,entry);
        tmp = (node*) malloc(sizeof(node));
        tmp->city = x;
        SLIST_INSERT_HEAD(links + y, tmp,entry);
    }
    bool *cheked = (bool*) calloc(n, sizeof(bool));
    super_list sl;
    SLIST_INIT(&sl);
    for(uint32_t i = 0; i < n; i++){
        if (!cheked[i]){
            super_node *sn = construct_node(i, n, links, cheked);
            SLIST_INSERT_HEAD(&sl, sn, entry);
        }
    }
    uint32_t size = 0;
    super_node *cur;
    SLIST_FOREACH(cur, &sl, entry) size++;
    if (size > 1){
        printf("%d\n", size - 1);
        uint32_t the_chosen = SLIST_FIRST(&SLIST_FIRST(&sl)->l)->city;
        SLIST_REMOVE_HEAD(&sl, entry);
        SLIST_FOREACH(cur, &sl, entry) printf("%d %d\n", the_chosen + 1, SLIST_FIRST(&cur->l)->city + 1);
    } else {
        printf("%d\n", size-1);
    }


    return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED