Problem

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example
Given n = 2, prerequisites = [[1,0]]
Return true

Given n = 2, prerequisites = [[1,0],[0,1]]
Return false

思路

• get indegrees.

• because courses are labeled from 0 to n-1, use array

• put all zero-degree courses to queue

• while queue is not empty,

  • poll the front element from it,
  • count ++
  • loop through all its adjacent element
    • degree decrement
    • enqueue those zero-degree adjs
• if count == num of courses return true
• notice
  • you can build a graph, like List[]
  • or not, because we already have all edges

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        for (int[] edge: prerequisites) {
            indegrees[edge[0]] += 1;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int curt = queue.poll();
            count++;
            for (int[] edge: prerequisites) {
                if (edge[1] != curt) continue;
                int adj = edge[0];
                indegrees[adj]--;
                if (indegrees[adj] == 0) {
                    queue.offer(adj);
                }
            }
        }
        return numCourses == count;
    }

build graph

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List[] graph = new List[numCourses];

        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        for (int[] edge: prerequisites) {
            indegrees[edge[0]] += 1;
            graph[edge[1]].add(edge[0]);

        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int curt = queue.poll();
            count++;

            for (Object obj: graph[curt]) {
                int adj = (int)obj;
                indegrees[adj]--;
                if (indegrees[adj] == 0) {
                    queue.offer(adj);
                }
            }
        }
        return numCourses == count;
    }