7. 并查集

习题

#30011

⚡4⏳4

实现支持动态合并和连通性查询的整数并查集：

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

typedef struct IntDisjointSet IntDisjointSet;

IntDisjointSet *int_dsu_create(size_t count);
void int_dsu_destroy(IntDisjointSet *set);
bool int_dsu_union(
    IntDisjointSet *set,
    size_t left,
    size_t right,
    bool *out_merged
);
bool int_dsu_same(
    const IntDisjointSet *set,
    size_t left,
    size_t right,
    bool *out_same
);
bool int_dsu_component_size(
    const IntDisjointSet *set,
    size_t element,
    size_t *out_size
);

要求：

1. 初始时每个元素单独成集合；下标必须小于 count。
2. union 使用按大小或按秩合并，并查找时进行路径压缩。
3. 重复合并成功返回并设置 *out_merged = false；失败时不得修改输出对象和集合结构。
4. destroy(NULL) 安全；count == 0 可以创建空集合。
5. 分摊时间复杂度应达到 $O(\alpha (n))$，并说明所维护的不变式。