Leetcode 207 Course Schedule

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:

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.

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.

拓扑排序，维护入度为0的集合。首先放入所有入度为0的点，逐个引出这个原点所能到达的点并删除原点，如果被到达的点在删除这条原点到其的路径后入度为0，则将这个点放入集合内。

伪代码

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

require ‘set‘
def can_finish(num_courses, prerequisites)
  graph, neighbour = Hash.new{|hsh,key| hsh[key] = Set.new}, Hash.new{|hsh,key| hsh[key] = Set.new}
  prerequisites.each {|x,y| graph[x] << y; neighbour[y] << x}
  zero_degree, count = [], 0
  num_courses.times {|x| zero_degree << x if graph[x].empty?}
  while not zero_degree.empty?
    node = zero_degree.pop
    count += 1
    neighbour[node].each do |x|
      graph[x] -= [node]
      zero_degree << x if graph[x].empty?
    end
  end
  count == num_courses
end

Leetcode 207 Course Schedule

原文：http://www.cnblogs.com/lilixu/p/4570835.html