31002：拓扑排序

题目

在有向 IntGraph 上生成包含每个顶点恰好一次的拓扑序，并区分参数错误、内存失败和图中存在环的情况。

解析

Kahn 算法先统计每个顶点的入度，把入度为零的顶点放入队列。弹出一个顶点后删除它的出边；某个邻接顶点入度降为零时再入队。若最终输出数量小于顶点数，剩余顶点都在环中。

拓扑序先写入临时数组，只有完整成功时才复制到调用方数组，所以容量不足和环都不会留下部分结果。

答案

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

typedef struct GraphEdge GraphEdge;
typedef struct IntGraph IntGraph;

struct GraphEdge {
    size_t to;
    GraphEdge *next;
};

typedef struct {
    GraphEdge *head;
    GraphEdge *tail;
} Adjacency;

struct IntGraph {
    Adjacency *adj;
    size_t vertex_count;
    bool directed;
};

typedef enum {
    GRAPH_TOPO_OK,
    GRAPH_TOPO_INVALID,
    GRAPH_TOPO_CYCLE
} GraphTopoResult;

GraphTopoResult int_graph_topological_order(
    const IntGraph *graph,
    size_t *out_order,
    size_t capacity,
    size_t *out_count
) {
    if (graph == NULL || !graph->directed || out_count == NULL ||
        capacity < graph->vertex_count ||
        (graph->vertex_count > 0 && out_order == NULL) ||
        graph->vertex_count > SIZE_MAX / sizeof(size_t)) {
        return GRAPH_TOPO_INVALID;
    }
    if (graph->vertex_count == 0) {
        *out_count = 0;
        return GRAPH_TOPO_OK;
    }
    size_t *indegree = calloc(
        graph->vertex_count, sizeof *indegree
    );
    size_t *queue = malloc(
        graph->vertex_count * sizeof *queue
    );
    size_t *order = malloc(
        graph->vertex_count * sizeof *order
    );
    if (indegree == NULL || queue == NULL || order == NULL) {
        free(indegree);
        free(queue);
        free(order);
        return GRAPH_TOPO_INVALID;
    }

    for (size_t vertex = 0;
         vertex < graph->vertex_count;
         ++vertex) {
        for (GraphEdge *edge = graph->adj[vertex].head;
             edge != NULL;
             edge = edge->next) {
            if (edge->to >= graph->vertex_count ||
                indegree[edge->to] == SIZE_MAX) {
                free(indegree);
                free(queue);
                free(order);
                return GRAPH_TOPO_INVALID;
            }
            ++indegree[edge->to];
        }
    }

    size_t front = 0;
    size_t back = 0;
    for (size_t vertex = 0;
         vertex < graph->vertex_count;
         ++vertex) {
        if (indegree[vertex] == 0) {
            queue[back++] = vertex;
        }
    }

    size_t written = 0;
    while (front < back) {
        size_t vertex = queue[front++];
        order[written++] = vertex;
        for (GraphEdge *edge = graph->adj[vertex].head;
             edge != NULL;
             edge = edge->next) {
            --indegree[edge->to];
            if (indegree[edge->to] == 0) {
                queue[back++] = edge->to;
            }
        }
    }

    if (written != graph->vertex_count) {
        free(indegree);
        free(queue);
        free(order);
        return GRAPH_TOPO_CYCLE;
    }
    memcpy(out_order, order, written * sizeof *out_order);
    *out_count = written;
    free(indegree);
    free(queue);
    free(order);
    return GRAPH_TOPO_OK;
}

入度统计和出边处理都只遍历一次，因此时间复杂度为 $O(V+E)$，额外空间为 $O(V)$。