Similar Problems
Similar Problems not available
Course Schedule Iv - Leetcode Solution
Companies:
LeetCode: Course Schedule Iv Leetcode Solution
Difficulty: Medium
Topics: graph depth-first-search breadth-first-search
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:
- 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.
- 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.
- 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.
Course Schedule Iv Solution Code
1There are a total of n courses you have to take, labeled from 0 to n-1.
2
3Some 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]
4
5Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
6
7Example 1:
8
9Input: 2, [[1,0]]
10Output: true
11Explanation: There are a total of 2 courses to take.
12 To take course 1 you should have finished course 0. So it is possible.
13Example 2:
14
15Input: 2, [[1,0],[0,1]]
16Output: false
17Explanation: There are a total of 2 courses to take.
18 To take course 1 you should have finished course 0, and to take course 0 you should
19 also have finished course 1. So it is impossible.
20Note:
21
22The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
23You may assume that there are no duplicate edges in the input prerequisites.
24
25
26
27class Solution {
28public:
29 bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
30
31 //Create a vector of vector to store the graph as an adjacency list
32 vector<vector<int>> adj(numCourses);
33
34 //Create a vector to store the indegree of each node
35 vector<int> indegree(numCourses, 0);
36
37 //Loop through the prerequisites and fill the adjacency list and indegree array
38 for(int i = 0; i < prerequisites.size(); i++) {
39 adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
40 indegree[prerequisites[i][0]]++;
41 }
42
43 //Create a queue to do BFS
44 queue<int> q;
45
46 //Add all the nodes with indegree 0 to the queue
47 for(int i = 0; i < numCourses; i++) {
48 if(indegree[i] == 0) {
49 q.push(i);
50 }
51 }
52
53 //Variable to keep track of the nodes visited
54 int visited = 0;
55
56 //Do BFS
57 while(!q.empty()) {
58 int node = q.front();
59 q.pop();
60 visited++;
61 for(int i = 0; i < adj[node].size(); i++) {
62 indegree[adj[node][i]]--;
63 if(indegree[adj[node][i]] == 0) {
64 q.push(adj[node][i]);
65 }
66 }
67 }
68
69 //If the number of visited nodes is equal to the number of courses, then return true. Else, return false
70 return visited == numCourses;
71 }
72};