Course ScheduleTotal Accepted: 3707 Total Submissions: 18102
There are a total of n courses you have to take, labeled from 0 ton – 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.
Note:The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more abouthow a graph is represented.
[思路]
此问题等价于 图(or forest)中有无环的存在.
使用topological sorting, 成功sort后,如果prerequisite没有空,则没有环.
[CODE]
public class Solution {// [4, 3] [3,2] [2,1]//init check.public boolean canFinish(int numCourses, int[][] prerequisites) {Set<int[]> pre = new HashSet<int[]>();for(int[] e : prerequisites) {pre.add(e);}int n = pre.size();if(n > numCourses*(numCourses-1)/2) return false;while(!getEnds(pre).isEmpty() ){};return pre.isEmpty();}// [1,2] [2, 3] [3,4]private Set<Integer> getEnds(Set<int[]> pre) {Set<Integer> set = new HashSet<Integer>();for(int[] arr : pre) {set.add(arr[0]);}for(int[] arr: pre) {set.remove(arr[1]);}Iterator<int[]> iter = pre.iterator();while(iter.hasNext() ) {int[] arr = iter.next();if(set.contains(arr[0]) ) iter.remove();}return set;}}
，知已知彼，百战百胜。
