There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
if there is a cycle that means it would be impossible to complete all courses . only 42 test cases are passing out of 52 what am i doing wrong
class Solution {
public:
bool finish(int course, unordered_map<int, list<int>>& adj,
vector<int> visited) {
visited[course] = 1;
queue<pair<int, int>> q;
q.push({course, -1});
while (!q.empty()) {
int node = q.front().first;
int parent = q.front().second;
q.pop();
for (auto it : adj[node]) {
if (!visited[it]) {
visited[it] = 1;
q.push({it, node});
}
else if (parent != it) {
return false;
}
}
}
return true;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, list<int>> adj;
for (int i = 0; i < prerequisites.size(); i++) {
int u = prerequisites[i][0];
int v = prerequisites[i][1];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> visited(numCourses, 0);
for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (!finish(i, adj, visited)) {
return false;
}
}
}
return true;
}
};
this is my code
There are a few issues:
The description is about a directed graph, yet you define each edge in both directions, making it an undirected graph. This is not correctly reflecting the problem
If there are two paths that start in distinct nodes (each starting in canFinish), but which arrive at the same node, this doesn't mean there is a cycle, yet your code identifies such a situation as a cycle. It doesn't help that you use a bread-first traversal. You could use a depth-first traversal and then mark the nodes that are on the current path with a specific value in visited. Once you have visited all children of a node, you can mark that node with another value, to indicate it is no longer on the path. Only when you encounter a node that is already on the current path, you have a cycle.
You haven't passed visited by reference, and so a copy is used in the finish function, which doesn't affect the caller's vector.
Here is a fix:
class Solution {
public:
bool finish(int course, unordered_map<int, list<int>>& adj,
vector<int> &visited) { // Pass by reference!
visited[course] = 1; // Use a distinct value for a node one the current path
for (auto it : adj[course]) { // Not breadth-first, but depth-first
if (visited[it] == 1 || !visited[it] && !finish(it, adj, visited)) {
return false;
}
}
visited[course] = 2; // Completed
return true;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int, list<int>> adj;
for (int i = 0; i < prerequisites.size(); i++) {
int u = prerequisites[i][0];
int v = prerequisites[i][1];
adj[v].push_back(u); // The graph is directed. No back reference!
}
vector<int> visited(numCourses, 0);
for (int i = 0; i < numCourses; i++) {
if (!visited[i] && !finish(i, adj, visited)) {
return false;
}
}
return true;
}
};