diff options
-rw-r--r-- | course_schedule4.c | 80 | ||||
-rw-r--r-- | course_schedule4.py | 53 |
2 files changed, 133 insertions, 0 deletions
diff --git a/course_schedule4.c b/course_schedule4.c new file mode 100644 index 0000000..d3f4fff --- /dev/null +++ b/course_schedule4.c @@ -0,0 +1,80 @@ +// 1462. Course Schedule IV +#include "leetcode.h" + +/* + * there are a total of 'numCourses' courses that you have to take, labeled from + * 0 to 'numCourses - 1'. you are given an array 'prerequisites' where + * 'prerequisites[i] = [a_i, b_i]' indicates that you must take course 'a_i' + * before 'b_i'. prerequisites can also be indirect. if course 'a' is a + * prerequisite of course 'b', and course 'b' is a prerequisite of course 'c', + * then course 'a' is a prerequisite of course 'c'. you are also given an array + * 'queries' where 'queries[j] = [u_j, v_j]'. for the j'th query, you should + * answer whether course 'u_j' is a prerequisite of course 'v_j' or not. + */ + +bool *checkIfPrerequisite(int numCourses, int **prerequisites, + int prerequisitesSize, int *prerequisitesColSize, + int **queries, int queriesSize, int *queriesColSize, + int *returnSize) { + *returnSize = queriesSize; + bool *ans = (bool *)malloc(queriesSize * sizeof(bool)); + bool **connected = (bool **)malloc(numCourses * sizeof(bool *)); + for (int i = 0; i < numCourses; i++) + connected[i] = (bool *)calloc(numCourses, sizeof(bool)); + for (int i = 0; i < prerequisitesSize; i++) { + int a = prerequisites[i][0]; + int b = prerequisites[i][1]; + connected[a][b] = true; + } + for (int k = 0; k < numCourses; k++) + for (int i = 0; i < numCourses; i++) + for (int j = 0; j < numCourses; j++) + if (connected[i][k] && connected[k][j]) + connected[i][j] = true; + for (int i = 0; i < queriesSize; i++) { + int u = queries[i][0]; + int v = queries[i][1]; + ans[i] = connected[u][v]; + } + for (int i = 0; i < numCourses; i++) + free(connected[i]); + free(connected); + return ans; +} + +int main() { + int p1i[1][2] = {{1, 0}}, q1i[2][2] = {{0, 1}, {1, 0}}, rs1; + int p2i[1][0] = {{}}, q2i[2][2] = {{1, 0}, {0, 1}}, rs2; + int p3i[3][2] = {{1, 2}, {1, 0}, {2, 0}}, q3i[2][2] = {{1, 0}, {1, 2}}, rs3; + struct two_d_arr p1, q1, p2, q2, p3, q3; + two_d_arr_init(&p1, ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i); + two_d_arr_init(&p2, 0, ARRAY_SIZE(p2i[0]), p2i); + two_d_arr_init(&p3, ARRAY_SIZE(p3i), ARRAY_SIZE(p3i[0]), p3i); + two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i); + two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i); + two_d_arr_init(&q3, ARRAY_SIZE(q3i), ARRAY_SIZE(q3i[0]), q3i); + bool *cip1 = checkIfPrerequisite(2, p1.arr, p1.row_size, p1.col_size, q1.arr, + q1.row_size, q1.col_size, &rs1); + bool *cip2 = checkIfPrerequisite(2, p2.arr, p2.row_size, p2.col_size, q2.arr, + q2.row_size, q2.col_size, &rs2); + bool *cip3 = checkIfPrerequisite(3, p3.arr, p3.row_size, p3.col_size, q3.arr, + q3.row_size, q3.col_size, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", cip1[i]); // expect: 0 1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", cip2[i]); // expect: 0 0 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", cip3[i]); // expect: 1 1 + printf("\n"); + free(cip1); + free(cip2); + free(cip3); + two_d_arr_free(&p1); + two_d_arr_free(&p2); + two_d_arr_free(&p3); + two_d_arr_free(&q1); + two_d_arr_free(&q2); + two_d_arr_free(&q3); +} diff --git a/course_schedule4.py b/course_schedule4.py new file mode 100644 index 0000000..9f9b21d --- /dev/null +++ b/course_schedule4.py @@ -0,0 +1,53 @@ +# 1462. Course Schedule IV + +""" +there are a total of 'numCourses' courses that you have to take, labeled from +0 to 'numCourses - 1'. you are given an array 'prerequisites' where +'prerequisites[i] = [a_i, b_i]' indicates that you must take course 'a_i' +before 'b_i'. prerequisites can also be indirect. if course 'a' is a +prerequisite of course 'b', and course 'b' is a prerequisite of course 'c', +then course 'a' is a prerequisite of course 'c'. you are also given an array +'queries' where 'queries[j] = [u_j, v_j]'. for the j'th query, you should +answer whether course 'u_j' is a prerequisite of course 'v_j' or not. +""" + + +class Solution(object): + def checkIfPrerequisite(self, numCourses, prerequisites, queries): + """ + :type numCourses: int + :type prerequisites: List[List[int]] + :type queries: List[List[int]] + :rtype: List[bool] + """ + connected = [[False] * numCourses for i in range(numCourses)] + for i, j in prerequisites: + connected[i][j] = True + for k in range(numCourses): + for i in range(numCourses): + for j in range(numCourses): + connected[i][j] = connected[i][j] or ( + connected[i][k] and connected[k][j] + ) + return [connected[i][j] for i, j in queries] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.checkIfPrerequisite( + numCourses=2, prerequisites=[[1, 0]], queries=[[0, 1], [1, 0]] + ) + ) + print( + obj.checkIfPrerequisite( + numCourses=2, prerequisites=[], queries=[[1, 0], [0, 1]] + ) + ) + print( + obj.checkIfPrerequisite( + numCourses=3, + prerequisites=[[1, 2], [1, 0], [2, 0]], + queries=[[1, 0], [1, 2]], + ) + ) |