31102：Kruskal 最小生成树

题目

给定无向带权图，求最小生成树总权重；图不连通或权重累加溢出时失败。

解析

Kruskal 按边权非递减排序，每次用并查集判断两个端点是否已经连通。若不连通就加入这条边并合并集合；若已经连通，加入它会产生环。处理完后必须恰好选出 vertex_count - 1 条边。

答案

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

typedef struct {
    size_t left;
    size_t right;
    uint64_t weight;
} UndirectedEdge;

static int compare_edges(const void *left, const void *right) {
    const UndirectedEdge *a = left;
    const UndirectedEdge *b = right;
    if (a->weight < b->weight) {
        return -1;
    }
    if (a->weight > b->weight) {
        return 1;
    }
    return 0;
}

static size_t dsu_find(size_t *parent, size_t element) {
    size_t root = element;
    while (parent[root] != root) {
        root = parent[root];
    }
    while (parent[element] != element) {
        size_t next = parent[element];
        parent[element] = root;
        element = next;
    }
    return root;
}

bool minimum_spanning_tree_weight(
    size_t vertex_count,
    const UndirectedEdge *edges,
    size_t edge_count,
    uint64_t *out_weight
) {
    if (out_weight == NULL ||
        (edge_count > 0 && edges == NULL)) {
        return false;
    }
    if (vertex_count == 0) {
        *out_weight = 0;
        return true;
    }
    if (vertex_count > SIZE_MAX / sizeof(size_t) ||
        edge_count > SIZE_MAX / sizeof(UndirectedEdge)) {
        return false;
    }
    for (size_t i = 0; i < edge_count; ++i) {
        if (edges[i].left >= vertex_count ||
            edges[i].right >= vertex_count) {
            return false;
        }
    }
    size_t *parent = malloc(vertex_count * sizeof *parent);
    size_t *sizes = malloc(vertex_count * sizeof *sizes);
    UndirectedEdge *copy = edge_count == 0
        ? NULL
        : malloc(edge_count * sizeof *copy);
    if (parent == NULL || sizes == NULL ||
        (edge_count > 0 && copy == NULL)) {
        free(parent);
        free(sizes);
        free(copy);
        return false;
    }
    for (size_t i = 0; i < vertex_count; ++i) {
        parent[i] = i;
        sizes[i] = 1;
    }
    if (edge_count > 0) {
        for (size_t i = 0; i < edge_count; ++i) {
            copy[i] = edges[i];
        }
        qsort(copy, edge_count, sizeof *copy, compare_edges);
    }

    size_t selected = 0;
    uint64_t total = 0;
    for (size_t i = 0;
         i < edge_count && selected < vertex_count - 1;
         ++i) {
        size_t left = dsu_find(parent, copy[i].left);
        size_t right = dsu_find(parent, copy[i].right);
        if (left == right) {
            continue;
        }
        if (sizes[left] < sizes[right]) {
            size_t temporary = left;
            left = right;
            right = temporary;
        }
        if (total > UINT64_MAX - copy[i].weight) {
            free(parent);
            free(sizes);
            free(copy);
            return false;
        }
        total += copy[i].weight;
        parent[right] = left;
        sizes[left] += sizes[right];
        ++selected;
    }

    bool connected = selected == vertex_count - 1;
    if (connected) {
        *out_weight = total;
    }
    free(parent);
    free(sizes);
    free(copy);
    return connected;
}

排序为 $O(E\log E)$，并查集操作的总成本为近似线性，整体达到 $O(E\log E)$；复制边数组和并查集占用 $O(E+V)$ 空间。