[Java] Simple Topological Sort Based Solution


#1
public class Solution {
    public int solve(int A, int[] B, int[] C) {
        
        int[] indegree = new int[A+1]; // since courses start from 1,2...
        Map<Integer, Set<Integer>> neighbors = new HashMap<>();

        for (int i=0; i<B.length; i++) {
            // create adjSet for src vertices
            if (!neighbors.containsKey(B[i])) neighbors.put(B[i], new HashSet<>());
            neighbors.get(B[i]).add(C[i]);
            
            // set indegree for dest vertices
            indegree[C[i]]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for (int i=1; i<indegree.length; i++)
            if (indegree[i] == 0) 
                q.add(i); // initialize queue with all courses with no pre-req

        int coursesTaken = 0;
        while (!q.isEmpty()) {
            int currentCourse = q.poll();
            coursesTaken++;
            
            if (neighbors.containsKey(currentCourse))
                for (int depCourse : neighbors.get(currentCourse))
                    // as soon as indegree becomes 0, we add that course to queue
                    if (--indegree[depCourse] == 0) q.add(depCourse);
        }
        
        return coursesTaken == A ? 1 : 0;
    }
}