[C language brush leetcode] 1462. curriculum IV (m)

【

You need a total of  numCourses  Course , The course numbers are 0  To  numCourses-1 . You'll get an array  prerequisite , among  prerequisites[i] = [ai, bi]  If you want to choose  bi Course , you must Choose... First  ai  Course .

Some classes have direct prerequisite courses , For example, if you want to take a course 1 , You must take the course first 0 , Then it will be [0,1]  The number of prerequisite courses is given in the form of number pairs .
The prerequisite can also be indirect Of . If the course a It's a course b prerequisites , Course b It's a course c prerequisites , So the course a It's the course c prerequisites .

You also get an array  queries , among  queries[j] = [uj, vj]. For the first j A query , You should answer the course  uj  Is it a course  vj  prerequisites .

Returns a Boolean array answer , among answer[j] It's No j The answer to a query .

Example 1：

Input ：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output ：[false,true]
explain ： Course 0 Not a course 1 A prerequisite course for , But the course 1 It's a course 0 A prerequisite course for .
Example 2：

Input ：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output ：[false,false]
explain ： There is no prerequisite course for , So each course is independent .
Example 3：

Input ：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output ：[true,true]
 

Tips ：

2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
Each pair of  [ai, bi]  all Different
There is no ring in the prerequisite course map .
0 <= ui, vi <= n - 1
ui != vi

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/course-schedule-iv
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

】

A violent meal takes time 196ms, result AC 了

bool* checkIfPrerequisite(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
    int i, j, k;
    int carr[numCourses][numCourses];
    bool *retarr;

    retarr = (bool *)malloc(sizeof(bool) * queriesSize);
    *returnSize = queriesSize;

    memset(carr, 0, sizeof(carr));

    for (i = 0; i < prerequisitesSize; i++) {
        carr[prerequisites[i][0]][prerequisites[i][1]] = 1; //  Record the relationship between the pre selected courses given 
    }

    for (i = 0; i < numCourses; i++) { //  Find out all the relationships between the first courses , violence 
        for (j = 0; j < numCourses; j++) {
            if (carr[i][j] == 1) {
                for (k = 0; k < numCourses; k++) {
                    if (carr[k][i] == 1) {
                        carr[k][j] = 1;
                    }
                }
            }
        }
    }

    for (i = 0; i < queriesSize; i++) {
        if (carr[queries[i][0]][queries[i][1]] == 1) {
            retarr[i] = true;
        } else {
            retarr[i] = false;
        }
    }

    return retarr;
}