[leetcode]Course Schedule

就是建立有向图 查有没有cycle

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

public class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { HashMap<Integer, Node> lookup = new HashMap<Integer, Node>(); for (int i = 0; i < prerequisites.length; i++){ Node temp = lookup.containsKey(prerequisites[i][0])? lookup.get(prerequisites[i][0]):new Node(prerequisites[i][0]); Node next = lookup.containsKey(prerequisites[i][1])? lookup.get(prerequisites[i][1]):new Node(prerequisites[i][1]); temp.addNext(next); lookup.put(prerequisites[i][0], temp); lookup.put(prerequisites[i][1], next); } Integer[]nodes = (Integer[])lookup.keySet().toArray(new Integer[lookup.size()]); for (int i = 0; i < nodes.length; i++){ if (!lookup.get(nodes[i]).checked && hasCycle(lookup, new HashSet<Integer>(), nodes[i].intValue())){ return false; } } return true; } public boolean hasCycle(HashMap<Integer, Node> lookup, HashSet<Integer> visited, int current){ Node curNode = lookup.get(current); curNode.checked = true; visited.add(current); List<Node> neighbors = curNode.nexts; for (int i = 0; i < neighbors.size(); i++){ if (visited.contains(neighbors.get(i).classNum) || hasCycle(lookup, visited, neighbors.get(i).classNum)){ return true; } } visited.remove(current); return false; } } class Node{ int classNum; boolean checked; List<Node> nexts = new ArrayList<Node>(); Node(int classNum){this.classNum = classNum;} void addNext(Node next){nexts.add(next);} }