1136. Parallel Courses

T: O(V+E)
S: O(n)

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<Integer>[] graph = new ArrayList[n+1];
        int[] indegree = new int[n+1];
        
        for (int i = 1; i < n+1; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] relation : relations) {
            graph[relation[0]].add(relation[1]);
            indegree[relation[1]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < n+1; i++) {
             // if there is a cycle, queue will empty! because indegree will not 0
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int count = 0;
        int semesters = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cur = queue.poll();
                count++;
                for (int next : graph[cur]) {
                    indegree[next]--;
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
            semesters++;
        }
        return count == n ? semesters : -1;
    }
}
/*
ask
minimum number of semesters

if cycle: return -1

are n courses labeled from 1 to n.: so size is n+1


how to handle cycle? it will correct in classical 210 ways
cycle example will return -1, because indregree are all not 0, so queue will empty
3
[[1,2],[2,3],[3,1]]

even if there is a another node
4
[[4,1], [1,2],[2,3],[3,1]]

4,1 => the count will be 1
cant finished all course, so return -1


T: O(V+E)
S: O(n)
*/ja