Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public boolean canFinish(int numCourses, int[][] prerequisites) {
- if(prerequisites.length == 0)
- return true;
- // Step-1 Create a adjacency list
- ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
- for(int i=0; i<numCourses; i++)
- {
- adj.add(new ArrayList<>());
- }
- // Step-2 Fill adjacency list and indegree array
- int[] indegree = new int[numCourses];
- for(int[] edge : prerequisites)
- {
- int u = edge[1];
- int v = edge[0];
- adj.get(u).add(v);
- indegree[v]++;
- }
- // Step-3 Find courses whose indegree is 0, add it to queue
- Queue<Integer> q = new LinkedList<>();
- for(int i=0; i<indegree.length; i++)
- {
- if(indegree[i] == 0)
- q.add(i);
- }
- // Step-4: Process queue
- int count = 0;
- while(!q.isEmpty())
- {
- int node = q.poll();
- count++;
- for(int u : adj.get(node))
- {
- indegree[u]--;
- if(indegree[u] == 0)
- q.add(u);
- }
- }
- // if cycle exisits then we cannot finish all courses
- if(count != numCourses)
- return false;
- return true;
- }
- }
RAW Paste Data
Copied
