CourseSchedule

gistfile1.java

public class Solution {
    public class Course {
        boolean done;
        boolean visiting;
        List<Course> pre;
        public Course() {
            done = false;
            visiting = false;
            pre = new ArrayList<>();
        }
        public void addPre(Course dep) {
            pre.add(dep);
        }
        public boolean isCyclic() {
            if (done) return false;
            if (visiting) return true;
            visiting = true;
            for (Course c: pre) {
                if (c.isCyclic())
                    return true;
            }
            visiting = false;
            done = true;
            return false;
        }
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Course[] courses = new Course[numCourses];
        for (int i = 0; i < numCourses; i++) {
            courses[i] = new Course();
        }
        for (int[] tuple: prerequisites) {
            int c1 = tuple[0];
            int c2 = tuple[1];
            courses[c1].addPre(courses[c2]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (courses[i].isCyclic()) return false;
        }
        return true;
    }
}

//topological sort
public class Solution {
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> preMap = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            preMap.put(i, new HashSet<Integer>());
        }
        for (int[] tuple: prerequisites) {
            int c1 = tuple[0];
            int c2 = tuple[1];
            preMap.get(c2).add(c1);
        }
        Queue<Integer> q = new LinkedList<>();
        for (Iterator it = preMap.entrySet().iterator(); it.hasNext();) {
            Map.Entry entry = (Map.Entry) it.next();
            Set s = (Set)entry.getValue();
            if (s.size() == 0) {
                q.offer((int)entry.getKey());
                it.remove();
            }
        }
        while (q.size() != 0) {
            int cur = q.poll();
            for (Iterator it = preMap.entrySet().iterator(); it.hasNext();) {
                Map.Entry entry = (Map.Entry) it.next();
                Set s = (Set) entry.getValue();
                s.remove(cur);
                if (s.isEmpty()) {
                    q.offer((int)entry.getKey());
                    it.remove();
                }
            }
        }
        return preMap.isEmpty();
    }
}