LeetCode 刷题

#define ELEM_TYPE int

// Define the structure for a node in the queue
typedef struct Node {
    ELEM_TYPE data;
    struct Node* next;
} Node;

// Define the structure for the queue
typedef struct Queue {
    int size;
    Node* front;
    Node* rear;
} Queue;

// Function to create a new node
Node* createNode(ELEM_TYPE data) {
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to create an empty queue
Queue* createQueue() {
    Queue* queue = (Queue *)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

// Function to check if the queue is empty
bool isEmpty(Queue* queue) {
    return queue->size == 0;
}

// Function to enqueue an element into the queue
void enQueue(Queue* queue, ELEM_TYPE data) {
    Node* newNode = createNode(data);
    if (isEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    queue->size += 1;
}

// Function to dequeue an element from the queue
ELEM_TYPE deQueue(Queue* queue) {
    if (isEmpty(queue)) {
        return -1;
    }
    Node* temp = queue->front;
    ELEM_TYPE data = temp->data;
    queue->front = queue->front->next;
    queue->size -= 1;
    free(temp);
    return data;
}

int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize) {
    int indegree[numCourses];  // 每个节点的入度，入度为 0 表示不受其它节点影响 
    int **edges = (int **)malloc(numCourses * sizeof(int *));  // 二维数组, 记录每个节点影响的节点们
    int edgeNums[numCourses];  // 记录每个节点影响的节点数量, 用于动态扩展空间
    int *ans = (int *)malloc(numCourses * sizeof(int));
    
    // 初始化
    for (int i = 0; i < numCourses; ++i) {
        indegree[i] = 0;
        edgeNums[i] = 0;
        edges[i] = (int *)malloc(0 * sizeof(int));  // 后续按需扩展
    }
    
    // 遍历所有节点对
    for (int i = 0; i < prerequisitesSize; ++i) {
        int suff = prerequisites[i][0], pre = prerequisites[i][1];
        edgeNums[pre]++;  // suff 受到了 pre 影响, 故 pre 节点影响的节点数量 +1
        indegree[suff]++;  // suff 受到了 pre 影响，其入度要 +1
        edges[pre] = (int *)realloc(edges[pre], edgeNums[pre] * sizeof(int));  // 扩展内存
        edges[pre][edgeNums[pre] - 1] = suff;  // 在索引(pre, 最后位置) 记录 suff
    }

    Queue* queue = createQueue();
    // 入度所有不受影响的节点
    for(int i = 0; i < numCourses; ++i) {
        if (indegree[i] == 0) {
            enQueue(queue, i);
        }
    }
    int count = 0;
    while (!isEmpty(queue)) {
        ELEM_TYPE cur = deQueue(queue);
        ans[count++] = cur;

        // 遍历出队的节点影响的所有节点, 它们的受影响度将 -1
        for (int i = 0; i < edgeNums[cur]; ++i) {
            int x = edges[cur][i];
            indegree[x]--;
            if (indegree[x] == 0) {
                enQueue(queue, x);
            }
        }
    }

    for (int i = 0; i < numCourses; ++i) {
        free(edges[i]);
    }
    free(edges);
    
    // 判断结果队列长度，确定是否可以完成拓扑排序
    if (count == numCourses) {
        (*returnSize) = count;
    } else {
        (*returnSize) = 0;
    }
    return ans;
}

void dfs(int node, int* visited, int** edges, int* edgeNums, int* ans, int* cnt, bool* valid) {
    visited[node] = 1;
    
    for (int i = 0; i < edgeNums[node]; ++i) {
        int neigNode = edges[node][i];
        if (visited[neigNode] == 0) {
            dfs(neigNode, visited, edges, edgeNums, ans, cnt, valid);
            // 这行代码测试发现不是必须的, 为什么不是必须的？加上可以有剪枝（提前终止）的作用
            if (!(*valid)) {return;}
        } else if (visited[neigNode] == 1) {
            *valid = false;
            return;
        }
    }

    visited[node] = 2;
    ans[--(*cnt)] = node;
}

int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize) {
    int* visited = (int *)malloc(numCourses * sizeof(int));  // 记录每一个节点的访问状态
    int** edges = (int **)malloc(numCourses * sizeof(int *));  // 二维数组, 记录每个节点所有邻居节点
    int* edgeNums = (int *)malloc(numCourses * sizeof(int));  // 记录每个节点的邻居节点数量
    int* ans = (int *)malloc(numCourses * sizeof(int));
    int cnt = numCourses;
    bool valid = true;
    
    memset(visited, 0, numCourses * sizeof(int));
    memset(edgeNums, 0, numCourses * sizeof(int));
    for (int i = 0; i < numCourses; ++i) {
        edges[i] = (int *)malloc(0 * sizeof(int));
    }
    
    // 构建邻接表
    for (int i = 0; i < prerequisitesSize; ++i) {
        int suff = prerequisites[i][0], pre = prerequisites[i][1];  // edge: pre->suff
        edges[pre] = (int *)realloc(edges[pre], (edgeNums[pre] + 1) * sizeof(int));
        edges[pre][edgeNums[pre]] = suff;
        edgeNums[pre]++;
    }
    
    // DFS 遍历
    for (int i = 0; i < numCourses && valid; ++i) {
        if (!visited[i]) {
            dfs(i, visited, edges, edgeNums, ans, &cnt, &valid);
        }
    }
    
    // 释放内存
    for (int i = 0; i < numCourses; ++i) {
        free(edges[i]);
    }
    free(edges);
    free(visited);
    free(edgeNums);
    
    *returnSize = (cnt > 0 || !valid) ? 0 : numCourses;
    return ans;
}