Disjoint sets — Find and Union

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>

stdio.h supplies terminal input/output. stdlib.h declares conversion and allocation functions. string.h supplies string and memory utilities. ctype.h supplies isspace, and errno.h supplies conversion error reporting. Headers declare facilities; including them does not execute an operation.

/* Read one entire token; reject malformed, oversized and out-of-range input. */
int readToken(char text[], size_t capacity) {
    int ch; size_t used = 0; int fits = 1;

readToken receives a writable buffer and its capacity. ch is int so it can represent EOF as well as input characters. used counts stored characters, and fits starts as a success flag. One slot must remain for the null terminator.

    while ((ch = getchar()) != EOF && isspace((unsigned char)ch)) { }
    if (ch == EOF) return 0;

Read until a non-whitespace character appears. The unsigned-char cast supplies an allowed value to isspace. Return 0 if EOF arrives before a token begins.

    do {
        if (ch == 0) fits = 0;
        if (used + 1 < capacity) text[used++] = (char)ch;
        else fits = 0;

The do body handles the character already read. An embedded zero byte marks the token invalid. Store a character only while there is room for it and a null terminator; otherwise clear fits. Continue reading even after the buffer fills.

        ch = getchar();
    } while (ch != EOF && !isspace((unsigned char)ch));
    text[used] = '\0';
    return fits;
}

Read through the next whitespace or EOF, add a null character after the stored prefix, then return fits. A too-long token returns 0 rather than pretending that its stored prefix is the complete token.

int readInt(int *value) {
    char token[64], *end;
    if (!readToken(token, sizeof token)) return 0;

value is an output address. A 64-slot local buffer receives the token; a failed token read returns 0 before attempting conversion.

    errno = 0; long result = strtol(token, &end, 10);
    if (errno || end == token || *end || result < -1000000 || result > 1000000) return 0;

Reset errno before strtol. &end receives the stopping address. Reject conversion errors, no converted digits, leftover characters, or values outside -1,000,000 to 1,000,000. Thus 12x is not accepted as the integer 12.

    *value = (int)result; return 1;
}
int invalid(void) { puts("Invalid or incomplete input."); return 1; }

Store a validated integer through *value and return 1 from readInt. invalid is a separate helper that prints the error and returns 1 as main’s failure status; the same number has different roles in these two function contracts.

#define MAX_N 100
int parent[MAX_N], rankValue[MAX_N];

The fixed arrays have room for 100 elements. parent links represent a forest of sets. rankValue is a balancing estimate; after path compression it is not necessarily the current exact tree height.

int findSet(int x) {
    if (parent[x] != x) parent[x] = findSet(parent[x]);
    return parent[x];
}

A root satisfies parent[x] == x. Otherwise recursively find the parent’s representative and save that root back into parent[x]. Return the representative. This shortens future searches for the same element.

void unionSets(int x, int y) {
    int a = findSet(x), b = findSet(y);
    if (a == b) return;

unionSets first obtains representatives a and b. If they are already equal, the elements already belong to one set, so return without changing rank or parent links.

    if (rankValue[a] < rankValue[b]) parent[a] = b;
    else {
        parent[b] = a;
        if (rankValue[a] == rankValue[b]) ++rankValue[a];
    }
}

If a has lower rank, its parent becomes b. Otherwise attach b below a; when their ranks were equal, increase a’s rank. Only roots are joined, preserving a valid parent forest.

/* First n (1..100); then 1 x y: union, 2 x: find, 3: display, 0: exit. */
int main(void) {
    int n, command, x, y;
    if (!readInt(&n) || n < 1 || n > MAX_N) return invalid();
    for (int i = 0; i < n; ++i) { parent[i] = i; rankValue[i] = 0; }

The comment lists union, find, display and exit commands. Require n from 1 to 100. Each element i initially represents itself, with parent[i] = i and rank zero.

    while (readInt(&command)) {
        if (command == 0) return 0;
        if (command == 3) {
            printf("Representatives:");
            for (int i = 0; i < n; ++i) printf(" %d", findSet(i));
            putchar('\n'); continue;
        }

Command 0 returns success. Command 3 prints findSet(i) for every element; these calls can also compress paths. continue skips operand reading and begins the next command.

        if (!readInt(&x) || x < 0 || x >= n) return invalid();
        if (command == 1) {
            if (!readInt(&y) || y < 0 || y >= n) return invalid();
            unionSets(x,y); puts("Union complete.");

Other commands require x within 0 through n - 1. Union command 1 additionally reads and validates y, then joins the two sets. No array lookup uses a rejected element index.

        } else if (command == 2) printf("Find(%d): %d\n",x,findSet(x));
        else return invalid();
    }
    return invalid();
}

Command 2 prints x’s representative. Another command returns the standard error. If command reading ends before explicit command 0, the program also reports invalid/incomplete input.