本文共 2498 字，大约阅读时间需要 8 分钟。

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 1:

Input: 2, [[1,0]] Output: trueExplanation: 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: 2, [[1,0],[0,1]]Output: falseExplanation: 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.

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.

我的想法

拓扑排序无疑了。这里有一点需要注意的是，map的key应该是被依赖的点，而value是依赖于key的点。indegree中value是key的入度。需要注意剔除重复的依赖关系

public class Solution {
       public boolean canFinish(int numCourses, int[][] prerequisites) {
           Queue
   
     queue = new LinkedList<>();        HashMap
    
     > map = new HashMap<>();        HashMap
     
       indegree = new HashMap<>();        int counter = 0;                //initialize indegree and map        for(int i = 0; i < numCourses; i++) {
               map.put(i, new HashSet
      
       ());            indegree.put(i, 0);        }                //calculate the indegree of each courses        for(int[] seq : prerequisites) {
               //avoid repeated prerequisites            if(map.get(seq[1]).add(seq[0])) {
                   indegree.put(seq[0], indegree.get(seq[0]) + 1);            }        }                //put zero indegree points into the queue        for(int i = 0; i < numCourses; i++) {
               if(indegree.get(i) == 0) {
                   queue.offer(i);            }        }                //doing the topological sorting        while(!queue.isEmpty()){
               int preCourse = queue.poll();            counter++;            for(Integer nextCourse : map.get(preCourse)) {
                   indegree.put(nextCourse, indegree.get(nextCourse) - 1);                if(indegree.get(nextCourse) == 0) {
                       queue.offer(nextCourse);                }            }        }                return numCourses == counter;    }}
      
     
    
   

解答

转载地址：http://okqvb.baihongyu.com/