leetcode 210 runtime error

发布于 2022-09-01 15:59:42 字数 4419 浏览 16 评论 0

大家帮忙看一下
https://leetcode.com/problems/course-schedule-ii/
提示输入为1 [] 的时候有runtime error. 但是我代码中对没有约束的情况作了特判,不应该啊。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>


typedef enum VertexColor{
    WHITE, GRAY, BLACK
}VertexColor;

typedef struct Vertex {
    int n;
    int d;
    int f;
    VertexColor color;
} Vertex;

typedef struct Node {
    Vertex *ver;
    struct Node *next;
} Node;

void printGraph_AL(Node **graph, int vertexNum) {
    for (int i = 0; i < vertexNum; i++) {
        Node *p = graph[i];
        while (p) {
            printf("%d ", p->ver->n);
            p = p->next;
        }
        printf("\n");
    }
}

bool hasEdge(Node **graph, int start, int i)
{
    Node *p = graph[start];
    bool result = false;
    while (p) {
        if (p->ver->n == i) {
            result = true;
            break;
        }
        p = p->next;
    }
    return result;
}
void dfs_visit(Node **graph, int numCourses, Vertex *vertices, int vernum, int *time, Node **head, bool *backEdge) {
    *time += 1;
    vertices[vernum].d = *time; vertices[vernum].color = GRAY;
    for (int i = 0; i < numCourses; i++) {
        if (vertices[i].color == GRAY && hasEdge(graph, vernum, i)) {
            *backEdge = true;
        }
        if (hasEdge(graph, vernum, i) && vertices[i].color == WHITE)
            dfs_visit(graph, numCourses, vertices, i, time, head, backEdge);
    }
    *time += 1;
    vertices[vernum].f = *time; vertices[vernum].color = BLACK;

    Node *node = malloc(sizeof(Node));
    node->ver = &vertices[vernum];
    node->next = *head;
    *head = node;
}

int* findOrder(int numCourses, int** prerequisites, int prerequisitesRowSize, int prerequisitesColSize, int* returnSize) {
    int *result;
    // no constraint among courses
    if (!prerequisitesRowSize || prerequisites) {
        result = malloc(sizeof(int) * numCourses);
        for (int i = 0; i < numCourses; i++) {
            result[i] = i;
        }
        *returnSize = numCourses;
        return result;
    }

    Node **graph = malloc(sizeof(Node*) * numCourses);
    for (int i = 0; i < numCourses; i++) {
        graph[i] = NULL;
    }

    Vertex *vertices = malloc(sizeof(Vertex) * numCourses);
    for (int i = 0; i< numCourses; i++) {
        vertices[i].color = WHITE;
        vertices[i].n = i;
    }
    for (int i = 0; i < prerequisitesRowSize; i++) {
        int start = prerequisites[i][0], end = prerequisites[i][1];
        Node *p = malloc(sizeof(Node));
        p->ver = &vertices[end];
        p->next = graph[start];
        graph[start] = p;
    }
    //printGraph_AL(graph, numCourses);
    int time = 0;
    Node *head = NULL; // The topological sort resulting linked list
    bool backEdge = false;
    for (int i = 0; i < numCourses && !backEdge; i++) {
        if (vertices[i].color == WHITE)
            dfs_visit(graph, numCourses, vertices, i, &time, &head, &backEdge);
    }
    if (backEdge) {
        *returnSize = 0;
        return NULL; 
    }

    *returnSize = numCourses;
    result = malloc(sizeof(int) * (*returnSize));
    int i = 0;
    Node *p = head;
    while (p) {
        result[i++] = p->ver->n;
        p = p->next;
    }
    return result;
}

int main()
{
    int numCourses = 5;
    int prerequisitesColSize = 2;
    /*
    int data[][2] = {
        {0,1}, {0,4}, {1,2}, {1,4}, {2,3}, {4,3}
    };
    */
    int data[][2] = {
    };
    int prerequisitesRowSize = sizeof(data) / (sizeof(int)*prerequisitesColSize);

    int **prerequisites = malloc(sizeof(int*) * prerequisitesRowSize);
    for (int i = 0; i < prerequisitesRowSize; i++) {
        prerequisites[i] = malloc(sizeof(int) * prerequisitesColSize);
    }
    for (int i = 0; i < prerequisitesRowSize; i++) {
        for (int j = 0; j < prerequisitesColSize; j++) {
            prerequisites[i][j] = data[i][j];
        }
    }
    int n;
    printf("prerequisitesRowSize: %d\n", prerequisitesRowSize);
    int *result = findOrder(numCourses, prerequisites, prerequisitesRowSize, prerequisitesColSize, &n);
    for (int i = 0; i < n; i++) {
        printf("%d\n", result[i]);
    }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文