leetcode 210 runtime error
大家帮忙看一下
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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论