30011：动态连通性查询

题目

实现支持按大小合并、路径压缩、连通性查询和集合大小查询的整数并查集。

解析

parent[x] 指向父结点，根结点满足 parent[x] == x；根的 sizes 保存整个集合大小，非根结点的 sizes 不参与决策。按大小合并让树高受控，路径压缩又会在查找过程中把路径直接接到根。

所有下标先验证，再调用查找；这样失败路径不会修改集合。成功的 same 查询可以进行路径压缩，但不会改变连通关系。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

typedef struct IntDisjointSet IntDisjointSet;

struct IntDisjointSet {
    size_t *parent;
    size_t *sizes;
    size_t count;
};

IntDisjointSet *int_dsu_create(size_t count) {
    IntDisjointSet *set = malloc(sizeof *set);
    if (set == NULL) {
        return NULL;
    }
    set->parent = NULL;
    set->sizes = NULL;
    set->count = count;
    if (count > 0) {
        if (count > SIZE_MAX / sizeof *set->parent) {
            free(set);
            return NULL;
        }
        set->parent = malloc(count * sizeof *set->parent);
        set->sizes = malloc(count * sizeof *set->sizes);
        if (set->parent == NULL || set->sizes == NULL) {
            free(set->parent);
            free(set->sizes);
            free(set);
            return NULL;
        }
        for (size_t i = 0; i < count; ++i) {
            set->parent[i] = i;
            set->sizes[i] = 1;
        }
    }
    return set;
}

void int_dsu_destroy(IntDisjointSet *set) {
    if (set == NULL) {
        return;
    }
    free(set->parent);
    free(set->sizes);
    free(set);
}

static size_t find_root(IntDisjointSet *set, size_t element) {
    size_t root = element;
    while (set->parent[root] != root) {
        root = set->parent[root];
    }
    while (set->parent[element] != element) {
        size_t next = set->parent[element];
        set->parent[element] = root;
        element = next;
    }
    return root;
}

static size_t find_root_const(
    const IntDisjointSet *set,
    size_t element
) {
    while (set->parent[element] != element) {
        element = set->parent[element];
    }
    return element;
}

bool int_dsu_union(
    IntDisjointSet *set,
    size_t left,
    size_t right,
    bool *out_merged
) {
    if (set == NULL || out_merged == NULL ||
        left >= set->count || right >= set->count) {
        return false;
    }
    size_t left_root = find_root(set, left);
    size_t right_root = find_root(set, right);
    if (left_root == right_root) {
        *out_merged = false;
        return true;
    }
    if (set->sizes[left_root] < set->sizes[right_root]) {
        size_t temporary = left_root;
        left_root = right_root;
        right_root = temporary;
    }
    set->parent[right_root] = left_root;
    set->sizes[left_root] += set->sizes[right_root];
    *out_merged = true;
    return true;
}

bool int_dsu_same(
    const IntDisjointSet *set,
    size_t left,
    size_t right,
    bool *out_same
) {
    if (set == NULL || out_same == NULL ||
        left >= set->count || right >= set->count) {
        return false;
    }
    *out_same = find_root_const(set, left) ==
        find_root_const(set, right);
    return true;
}

bool int_dsu_component_size(
    const IntDisjointSet *set,
    size_t element,
    size_t *out_size
) {
    if (set == NULL || out_size == NULL || element >= set->count) {
        return false;
    }
    size_t root = find_root_const(set, element);
    *out_size = set->sizes[root];
    return true;
}

按大小合并保证树高为 $O(\log n)$，结合路径压缩后操作的摊还复杂度为 $O(\alpha (n))$。