package com.fishercoder.solutions;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class _207 {

    public static class Solution1 {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] indegree = new int[numCourses];
            for (int[] prereq : prerequisites) {
                indegree[prereq[0]]++;
            }
            Set<Integer> zeroDegree = new HashSet();
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0) {
                    zeroDegree.add(i);
                }
            }
            if (zeroDegree.isEmpty()) {
                return false;
            }

            while (!zeroDegree.isEmpty()) {
                Iterator<Integer> it = zeroDegree.iterator();
                int course = it.next();
                zeroDegree.remove(course);
                for (int[] prereq : prerequisites) {
                    if (prereq[1] == course) {
                        indegree[prereq[0]]--;
                        if (indegree[prereq[0]] == 0) {
                            zeroDegree.add(prereq[0]);
                        }
                    }
                }
            }

            for (int i : indegree) {
                if (i != 0) {
                    return false;
                }
            }
            return true;
        }
    }
}

@@ -82,16 +82,69 @@
 erator;%0A
+import java.util.LinkedList;%0Aimport java.util.Queue;%0A
 import j
@@ -157,16 +157,16 @@
 il.Set;%0A
-
 %0Apublic 
@@ -215,16 +215,70 @@
 tion1 %7B%0A
+        /**Kahn's algorithm for topological sorting*/%0A
         
@@ -1356,24 +1356,24 @@
 indegree) %7B%0A
-
             
@@ -1496,11 +1496,1184 @@
  %7D%0A    %7D
+%0A%0A    public static class Solution2 %7B%0A        /**%0A         * BFS%0A         */%0A        public boolean canFinish(int numCourses, int%5B%5D%5B%5D prerequisites) %7B%0A            int%5B%5D indegree = new int%5BnumCourses%5D;%0A            for (int%5B%5D pre : prerequisites) %7B%0A                indegree%5Bpre%5B0%5D%5D++;%0A            %7D%0A            Queue%3CInteger%3E queue = new LinkedList();%0A            for (int i = 0; i %3C numCourses; i++) %7B%0A                if (indegree%5Bi%5D == 0) %7B%0A                    queue.offer(i);%0A                %7D%0A            %7D%0A            if (queue.isEmpty()) %7B%0A                return false;%0A            %7D%0A            while (!queue.isEmpty()) %7B%0A                int course = queue.poll();%0A                for (int%5B%5D pre : prerequisites) %7B%0A                    if (pre%5B1%5D == course) %7B%0A                        indegree%5Bpre%5B0%5D%5D--;%0A                        if (indegree%5Bpre%5B0%5D%5D == 0) %7B%0A                            queue.offer(pre%5B0%5D);%0A                        %7D%0A                    %7D%0A                %7D%0A            %7D%0A            for (int degree : indegree) %7B%0A                if (degree != 0) %7B%0A                    return false;%0A                %7D%0A            %7D%0A            return true;%0A        %7D%0A    %7D
 %0A%7D%0A

refactor 207