Short Java Solution


  • 0
    Y
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // topological sort
            // preparation: a hashmap to represent the graph, and an array to keep indegrees of each vertex
            HashMap<Integer, List<Integer>> G = new HashMap<>();
            int[] indegrees = new int[numCourses];
            for (int[] p : prerequisites) {
                if (!G.containsKey(p[0])) {
                    G.put(p[0], new ArrayList<>());
                }
                G.get(p[0]).add(p[1]);
                indegrees[p[1]]++;
            }
            // perform topological sort until we have visited all courses
            // whenever we have visited a course with indegree == 0, we set it to -1 so it won't be visited again
            // it a topological sort exists, then we can visit all courses without return false
            for (int i = 0; i < numCourses; i++) {
                int course = -1;
                for (int j = 0; j < indegrees.length; j++) {
                    if (indegrees[j] == 0) {
                        course = j;
                        indegrees[j] = -1;
                        break;
                    }
                }
                if (course == -1) {
                    return false;
                }
                // course can be no prerequisite and doesn't exist in HashMap
                if (G.get(course) != null) {
                    for (int c : G.get(course)) {
                        indegrees[c]--;
                    }
                }
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.