Problem:
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 and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
|
1 |
2, [[1,0]] |
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
|
1 |
2, [[1,0],[0,1]] |
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.
Idea:
Finding cycles O(n^2) -> Topological sort O(n)
Solution 1: Topological Sort
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Author: Huahua // Time complexity: O(n) // Runtime: 12 ms class Solution { public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { graph_ = vector<vector<int>>(numCourses); for(const auto& p : prerequisites) graph_[p.first].push_back(p.second); // states: 0 = unkonwn, 1 == visiting, 2 = visited vector<int> v(numCourses, 0); for(int i = 0; i < numCourses; ++i) if(dfs(i, v)) return false; return true; } private: vector<vector<int>> graph_; bool dfs(int cur, vector<int>& v) { if(v[cur] == 1) return true; if(v[cur] == 2) return false; v[cur] = 1; for(const int t : graph_[cur]) if(dfs(t, v)) return true; v[cur] = 2; return false; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Author: Huahua // Runtime: 6 ms // HashMap is slower than ArrayList in this problem. class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for (int i = 0; i < numCourses; ++i) graph.add(new ArrayList<Integer>()); for (int i = 0; i < prerequisites.length; ++i) { int course = prerequisites[i][0]; int prerequisite = prerequisites[i][1]; graph.get(course).add(prerequisite); } int[] visited = new int[numCourses]; for (int i = 0; i < numCourses; ++i) if (dfs(i, graph, visited)) return false; return true; } private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited) { if (visited[curr] == 1) return true; if (visited[curr] == 2) return false; visited[curr] = 1; for (int next : graph.get(curr)) if (dfs(next, graph, visited)) return true; visited[curr] = 2; return false; } } |
Solution 2: DFS Finding cycles
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Author: Huahua // Time complexity: O(n^2) // Runtime: 179 ms class Solution { public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { graph_.clear(); for(const auto& p : prerequisites) graph_[p.first].insert(p.second); for (int i = 0; i < numCourses; ++i) { vector<int> visited(numCourses, 0); if (cycle(i, i, visited)) return false; } return true; } private: unordered_map<int, unordered_set<int>> graph_; bool cycle(int start, int curr, vector<int>& visited) { if (curr == start && visited[start]) return true; if (!graph_.count(curr)) return false; for (const int next : graph_.at(curr)) { if (visited[next]) continue; visited[next] = true; if (cycle(start, next, visited)) return true; } return false; } }; |