48.Course Schedule（课程安排）

####Level：

Medium

####题目描述：

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: 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: 2, [[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.

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.

####思路分析：

这题是拓扑排序一道应用，首先，我们应该统计每个点的入度，然后根据拓扑排序的规则，先删去入度为0的点，直到最后点的个数为0，则是正确的排课。

####代码：

public class Solution{

    public boolean canFinish(int coursenum,int[][]prerequisites){

        int []indegree=new int [coursenum];//记录每门课的入度。

        for(int []pair:prerequisites){

            indegree[pair[0]]++; //统计每门课的入度

        }

        Queue<Integer>q=new LinkedList<>(); //存放入度为0的课程，准备删除

        for(int i=0;i<coursenum;i++){

            if(indegree[i]==0)

                q.offer(i);

        }

        while(!q.isEmpty()){

            int key=q.poll();//删除一个入度为0的课程

            coursenum--;//课程数减1

            for(int[] pair:prerequisites){

                if(pair[1]==key){//因为删除了节点，那么和这个节点相连的节点入度减一。

                    indegree[pair[0]]--;

                if(indegree[pair[0]]==0)//如果减一后，这个节点的入度为0，则加入删除队列

                    q.offer(pair[0]);

                }

            }

        }

        return coursenum==0; //如果最终都被删除，则满足排课顺序

    }

}

巴特西

48.Course Schedule（课程安排）

最新文章

热门文章