GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Algorithm/java/coding/courseSchedule.java at master · lelea2/Algorithm Expand file tree/ Copy pathcourseSchedule.javaMore file actions 54 lines (45 loc) · 2 KB / Copy pathcourseSchedule.javaFile metadata and controls54 lines (45 loc) · 2 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 /** * 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, given 2 and [[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. * For another example, given 2 and [[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. */ //Idea: apply DFS or BFS algorithm //Checking if a graph contains a cycle //Solution with BFS public boolean canFinish(int numCourses, int[][] prerequisites) { if(prerequisites == null) { throw new IllegalArgumentException("illegal prerequisites array"); } int len = prerequisites.length; if(numCourses == 0 || len == 0) { return true; } // counter for number of prerequisites int[] pCounter = new int[numCourses]; for(int i=0; i<len; i++) { pCounter[prerequisites[i][0]]++; } //store courses that have no prerequisites LinkedList<Integer> queue = new LinkedList<Integer>(); for(int i=0; i<numCourses; i++) { if(pCounter[i]==0){ queue.add(i); } } // number of courses that have no prerequisites int numNoPre = queue.size(); while(!queue.isEmpty()) { int top = queue.remove(); for(int i=0; i<len; i++) { // if a course's prerequisite can be satisfied by a course in queue if(prerequisites[i][1]==top) { pCounter[prerequisites[i][0]]--; if(pCounter[prerequisites[i][0]]==0) { numNoPre++; queue.add(prerequisites[i][0]); } } } } return numNoPre == numCourses; } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |