[leetcode] course schedule

这条题就是把课的constraints 转化成有向图，然后dfs看所有生成的图有没有cycle
一开始 会time limit exceed.后来做pruning了 就过了..

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

public class Solution { boolean graph[][]; boolean check[]; int noCycleFromIndex[]; public boolean canFinish(int numCourses, int[][] prerequisites) { noCycleFromIndex = new int[numCourses]; graph = new boolean[numCourses][numCourses]; check = new boolean[numCourses]; for (int i = 0; i < prerequisites.length; i++){ graph[prerequisites[i][0]][prerequisites[i][1]] = true; } for(int i = 0; i < check.length; i++){ if (noCycleFromIndex[i] == -1 || !checkGraph(i)){ return false; } } return true; } private boolean checkGraph(int course){ if (check[course] || noCycleFromIndex[course] == -1){ return false; } if (noCycleFromIndex[course] == 1){ return true; } check[course] = true; for (int i = 0; i < check.length; i++){ if (graph[course][i]&&!checkGraph(i)){ noCycleFromIndex[course] = -1; return false; } } check[course] = false; noCycleFromIndex[course] = 1; return true; } }