31003：DFS、连通分量与有向环

题目

在 30012 的图表示上实现 DFS 顺序、无向连通分量统计和有向图环检测。

解析

DFS 递归函数在进入顶点时记录它，再按邻接链表顺序递归未访问邻接点，因此输出顺序直接对应题面要求。连通分量只对无向图运行，从每个尚未访问的顶点启动一次 DFS。

有向环检测使用白、灰、黑三色：白色表示未进入，灰色表示仍在当前递归路径，黑色表示已经完成。沿边遇到灰色顶点正是回边，说明存在有向环。所有结果先写入临时存储，失败路径不改调用方输出。

答案

#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;
};

static bool dfs_order_visit(
    const IntGraph *graph,
    size_t vertex,
    bool *visited,
    size_t *order,
    size_t *out_count
) {
    visited[vertex] = true;
    order[(*out_count)++] = vertex;
    for (GraphEdge *edge = graph->adj[vertex].head;
         edge != NULL;
         edge = edge->next) {
        if (edge->to >= graph->vertex_count) {
            return false;
        }
        if (!visited[edge->to] &&
            !dfs_order_visit(
                graph, edge->to, visited, order, out_count
            )) {
            return false;
        }
    }
    return true;
}

bool int_graph_dfs_order(
    const IntGraph *graph,
    size_t source,
    size_t *out_order,
    size_t capacity,
    size_t *out_count
) {
    if (graph == NULL || out_count == NULL ||
        source >= graph->vertex_count ||
        graph->vertex_count > SIZE_MAX / sizeof(bool) ||
        graph->vertex_count > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    bool *visited = calloc(graph->vertex_count, sizeof *visited);
    size_t *order = malloc(graph->vertex_count * sizeof *order);
    if (visited == NULL || order == NULL) {
        free(visited);
        free(order);
        return false;
    }
    size_t count = 0;
    bool valid = dfs_order_visit(
        graph, source, visited, order, &count
    );
    if (!valid || count > capacity ||
        (count > 0 && out_order == NULL)) {
        free(visited);
        free(order);
        return false;
    }
    memcpy(out_order, order, count * sizeof *out_order);
    *out_count = count;
    free(visited);
    free(order);
    return true;
}

static bool mark_component(
    const IntGraph *graph,
    size_t vertex,
    bool *visited
) {
    visited[vertex] = true;
    for (GraphEdge *edge = graph->adj[vertex].head;
         edge != NULL;
         edge = edge->next) {
        if (edge->to >= graph->vertex_count) {
            return false;
        }
        if (!visited[edge->to] &&
            !mark_component(graph, edge->to, visited)) {
            return false;
        }
    }
    return true;
}

bool int_graph_count_components(
    const IntGraph *graph,
    size_t *out_components
) {
    if (graph == NULL || graph->directed || out_components == NULL ||
        graph->vertex_count > SIZE_MAX / sizeof(bool)) {
        return false;
    }
    bool *visited = graph->vertex_count == 0
        ? NULL
        : calloc(graph->vertex_count, sizeof *visited);
    if (graph->vertex_count > 0 && visited == NULL) {
        return false;
    }
    size_t components = 0;
    for (size_t vertex = 0;
         vertex < graph->vertex_count;
         ++vertex) {
        if (!visited[vertex]) {
            if (components == SIZE_MAX ||
                !mark_component(graph, vertex, visited)) {
                free(visited);
                return false;
            }
            ++components;
        }
    }
    free(visited);
    *out_components = components;
    return true;
}

static bool cycle_visit(
    const IntGraph *graph,
    size_t vertex,
    unsigned char *color,
    bool *out_cycle
) {
    color[vertex] = 1;
    for (GraphEdge *edge = graph->adj[vertex].head;
         edge != NULL;
         edge = edge->next) {
        if (edge->to >= graph->vertex_count) {
            return false;
        }
        if (color[edge->to] == 1) {
            *out_cycle = true;
            return true;
        }
        if (color[edge->to] == 0 &&
            !cycle_visit(
                graph, edge->to, color, out_cycle
            )) {
            return false;
        }
        if (*out_cycle) {
            return true;
        }
    }
    color[vertex] = 2;
    return true;
}

bool int_graph_has_directed_cycle(
    const IntGraph *graph,
    bool *out_cycle
) {
    if (graph == NULL || !graph->directed || out_cycle == NULL ||
        graph->vertex_count > SIZE_MAX / sizeof(unsigned char)) {
        return false;
    }
    unsigned char *color = graph->vertex_count == 0
        ? NULL
        : calloc(graph->vertex_count, sizeof *color);
    if (graph->vertex_count > 0 && color == NULL) {
        return false;
    }
    bool cycle = false;
    for (size_t vertex = 0;
         vertex < graph->vertex_count && !cycle;
         ++vertex) {
        if (color[vertex] == 0 &&
            !cycle_visit(graph, vertex, color, &cycle)) {
            free(color);
            return false;
        }
    }
    free(color);
    *out_cycle = cycle;
    return true;
}

三种操作都检查每个顶点和邻接边至多一次，时间复杂度为 $O(V+E)$。递归调用帧最坏为 $O(V)$；若图深度可能很大，可以把帧显式放入拥有的堆栈数组。