Course Schedule Iv - Leetcode Solution

Problem Statement: There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses n, a list of prerequisite pairs, and an integer k, return the number of courses you must take to study all the courses.

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] Output: [false,true] Explanation: You can't take course 0 if you take course 1 first because of the dependency between them.

Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]] Output: [true,true] Explanation: There are no prerequisites, so it is possible to take any course.

Approach: The approach to this problem is to create a directed graph using the given prerequisite pairs, and topologically sort the graph using a queue. We can then perform a BFS for each query and check if it is possible to reach the destination course from the source course using the directed edges of the graph.

Algorithm:

1. Create a directed graph using the given prerequisite pairs. Each course is a node in the graph, and if there is a prerequisite from course A to course B, then there is a directed edge from A to B.
2. Topologically sort the graph using a queue. Initialize a queue to store all the courses with no prerequisites. For each course with no prerequisites, add it to the queue and mark it as visited. For each course in the queue, remove it from the queue, and for each course that has an incoming edge from the current course, decrement its incoming edge count. If any course becomes a course with no incoming edges after decrementing the count, add it to the queue and mark it as visited.
3. For each query (source, destination), perform a BFS search from the source course, and check if it is possible to reach the destination course using the directed edges of the graph. If it is possible, add true to the result list, otherwise add false.

Code:

class Solution { public: vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prereq, vector<vector<int>>& queries) { // Create the directed graph vector<vector<int>> graph(n); vector<int> incomingEdges(n, 0); for (auto p : prereq) { graph[p[0]].push_back(p[1]); incomingEdges[p[1]]++; }

    // Topologically sort the graph
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (incomingEdges[i] == 0) {
            q.push(i);
        }
    }
    vector<int> topologicalOrder;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        topologicalOrder.push_back(current);
        for (int neighbor : graph[current]) {
            incomingEdges[neighbor]--;
            if (incomingEdges[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // Create the adjacency matrix
    vector<vector<bool>> adjMatrix(n, vector<bool>(n, false));
    for (auto p : prereq) {
        adjMatrix[p[0]][p[1]] = true;
    }

    // Perform the queries
    vector<bool> result;
    for (auto query : queries) {
        int source = query[0];
        int destination = query[1];

        // Check if there is a path from the source to the destination in the directed graph
        vector<bool> visited(n, false);
        queue<int> bfs;
        bfs.push(source);
        visited[source] = true;
        bool found = false;
        while (!bfs.empty() && !found) {
            int current = bfs.front();
            bfs.pop();
            for (int i = 0; i < n; i++) {
                if (adjMatrix[current][i] && !visited[i]) {
                    if (i == destination) {
                        found = true;
                        break;
                    }
                    visited[i] = true;
                    bfs.push(i);
                }
            }
        }
        result.push_back(found);
    }
    return result;
}

};

Time Complexity: The time complexity of this solution is O(n^2 + m), where n is the number of courses and m is the number of prerequisite pairs. The O(n^2) time complexity is due to the creation of the adjacency matrix, and the O(m) time complexity is due to the BFS search for each query.

1