Topology sorting

directed graph

DFS

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = new ArrayList<>();

        for (int i = 0; i < numCourses; i++)
            edges.add(new ArrayList<Integer>());

        for (int[] pre: prerequisites){
            edges.get(pre[0]).add(pre[1]);
        }
        boolean[] visited = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (!canFinishHelper(i, visited, edges)) return false;
        }

        return true;
    }

    private boolean canFinishHelper(int course, boolean[] visited, List<List<Integer>> edges){
        if (visited[course]) return false;
        visited[course] = true;
        while (edges.get(course).size() != 0){
            for (int j = 0; j < edges.get(course).size(); j++) {
                if (!canFinishHelper(edges.get(course).get(j), visited, edges)) return false;
                edges.get(course).remove(j);
            }
        }
        visited[course] = false;
        return true;
    }
}

BFS

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //validate input 
        if (prerequisites.length == 0 || prerequisites[0].length == 0) return true;

        Map<Integer, List<Integer>> map = new HashMap<>();//key - prerequisite, value - courses can take after took this course
        Map<Integer, Integer> indegree = new HashMap<>();//key - course number, value - its indegree

        //count indegree
        for (int[] prere : prerequisites) {
            if (!map.containsKey(prere[1])) {
                map.put(prere[1], new ArrayList<>());
            }
            map.get(prere[1]).add(prere[0]);

            if (!indegree.containsKey(prere[0])) {
                indegree.put(prere[0], 0);
            }
            indegree.put(prere[0], indegree.get(prere[0]) + 1);
        }

        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        //add indegree 0s to queue
        for (int i = 0; i < numCourses; ++i) {
            if (!indegree.containsKey(i)) queue.offer(i);
        }

        //poll the element at the top, and then count++
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;

            if (map.containsKey(course)) {
                for (int num : map.get(course)) {
                    indegree.put(num, indegree.get(num) - 1);
                    if (indegree.get(num) == 0) queue.offer(num);
                }
            }
        }

        return count == numCourses;

    }
}