Course Schedule
update Jul 18, 2017 14:11
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?
Example
Given n = 2, prerequisites = [[1,0]]
Return true
Given n = 2, prerequisites = [[1,0],[0,1]]
Return false
Basic Idea:
这个问题就是问一个有向图能否被 topological sort，即有向图中是否有环。首先把input的形式转换为adjacent list的形式，然后用bfs和indegree count（Kahn's Algorithm）的方法检查能否topological sort。
Java Code:
public class Solution {
/**
* @param numCourses a total of n courses
* @param prerequisites a list of prerequisite pairs
* @return true if can finish all courses or false
*/
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses < 2) return true;
Map<Integer, Set<Integer>> graph = initGraph(numCourses, prerequisites);
// 得到adjacent list形式的图之后，用BFS进行topological sort，看是否可行
// 先count indegree
Map<Integer, Integer> count = new HashMap<>();
for (int node : graph.keySet()) {
count.put(node, 0);
}
for (int node : graph.keySet()) {
for (int neighbor : graph.get(node)) {
count.put(neighbor, count.get(neighbor) + 1);
}
}
// bfs
Deque<Integer> queue = new LinkedList<>();
for (int node : graph.keySet()) {
if (count.get(node) == 0) queue.addFirst(node);
}
while (! queue.isEmpty()) {
int node = queue.removeLast();
for (int neighbor : graph.get(node)) {
count.put(neighbor, count.get(neighbor) - 1);
if (count.get(neighbor) == 0) queue.addFirst(neighbor);
}
}
return Collections.max(count.values()) <= 0;
}
private Map<Integer, Set<Integer>> initGraph(int n, int[][] edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; ++i) {
graph.put(i, new HashSet<Integer>());
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
graph.get(u).add(v);
}
return graph;
}
}
Python Code:
class Solution:
# @param {int} numCourses a total of n courses
# @param {int[][]} prerequisites a list of prerequisite pairs
# @return {boolean} true if can finish all courses or false
# 这就是一个问图能否topological sort的问题，但是所给信息的形式是node + edges
# 的形式，我们还需要先将其转换为adjacent list的形式，即（Map<node, Set<neighbor>>）
def canFinish(self, numCourses, prerequisites):
def initGraph(n, edges):
graph = {}
for i in range(n):
graph[i] = set()
for edge in edges:
u, v = edge[0], edge[1]
graph[u].add(v)
return graph
if numCourses < 2: return True
graph = initGraph(numCourses, prerequisites)
# count indegree
count = {}
for i in range(numCourses):
count[i] = 0
for node in graph:
for neighbor in graph[node]:
count[neighbor] += 1
# bfs, topological sort
queue = collections.deque()
for node in graph:
if count[node] == 0:
queue.appendleft(node)
while queue:
node = queue.pop()
for neighbor in graph[node]:
count[neighbor] -= 1
if count[neighbor] == 0:
queue.appendleft(neighbor)
return not [node for node in graph if count[node] > 0]
update 2018-05-19 19:16:11
C++ Kahn's Algorithm, BFS Solution
class Solution {
vector<vector<int>>& initGraph(int size, vector<pair<int, int>>& edges) {
vector<vector<int>>& graph = *(new vector<vector<int>>(size));
for (auto& _pair : edges) {
graph[_pair.first].push_back(_pair.second);
}
return graph;
}
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
auto& graph = initGraph(numCourses, prerequisites);
unordered_map<int, int> _inDegree;
for (int i = 0; i < numCourses; ++i) {
_inDegree[i];
for (int neighbor : graph[i]) {
++_inDegree[neighbor];
}
}
deque<int> _queue;
for (auto& _pair : _inDegree) {
if (_pair.second == 0) _queue.push_back(_pair.first);
}
while (! _queue.empty()) {
int node = _queue.front();
_queue.pop_front();
for (int neighbor : graph[node]) {
if (--_inDegree[neighbor] == 0) {
_queue.push_back(neighbor);
}
}
}
for (auto& _pair : _inDegree) {
if (_pair.second > 0) return false;
}
return true;
}
};
C++ DFS Solution
如果在dfs中发现有环，则表示不可以，返回 false；
class Solution {
vector<vector<int>>& initGraph(int size, vector<pair<int, int>>& edges) {
vector<vector<int>>& graph = *(new vector<vector<int>>(size));
for (auto _pair : edges) {
graph[_pair.first].push_back(_pair.second);
}
return graph;
}
bool dfs(vector<vector<int>>& graph, int curr, unordered_set<int>& visited, unordered_set<int>& path) {
if (path.count(curr)) return false;
else if (visited.count(curr)) return true;
visited.insert(curr);
path.insert(curr);
for (int neighbor : graph[curr]) {
if (! dfs(graph, neighbor, visited, path)) return false;
}
path.erase(curr);
return true;
}
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>>& graph = initGraph(numCourses, prerequisites);
unordered_set<int> visited;
for (int i = 0; i < numCourses; ++i) {
if (visited.count(i)) continue;
unordered_set<int> path;
if (! dfs(graph, i, visited, path)) return false;
}
return true;
}
};
update 2018-06-19 21:29:29
Update 精简的C++，count indegree solution
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
// 生成图的同时统计 indegree
unordered_map<int, int> indegrees;
vector<vector<int>> graph(numCourses);
for (auto edge : prerequisites) {
graph[edge.second].push_back(edge.first);
indegrees[edge.first]++;
}
// BFS，降低neighbor的indegree，把降为0的node入队
deque<int> q;
for (int i = 0; i < numCourses; ++i) {
if (! indegrees.count(i)) q.push_back(i);
}
// 计数总入队node的个数，如果可以finish，必须所有node都入队，count需要等于numCourses
int count = 0;
while (! q.empty()) {
int curr = q.front(); q.pop_front();
for (int neighbor : graph[curr]) {
if (--indegrees[neighbor] == 0) {
q.push_back(neighbor);
}
}
++count;
}
return count == numCourses;
}
};