Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public int[] findOrder(int numCourses, int[][] prerequisites) {
- // Step 1: Create 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 prereq = edge[1];
- int course = edge[0];
- adj.get(prereq).add(course);
- indegree[course]++;
- }
- // Step 3: Queue for nodes with indegree 0
- Queue<Integer> q = new LinkedList<>();
- for(int i = 0; i < numCourses; i++)
- if(indegree[i] == 0)
- q.add(i);
- // Step 4: Topological Sort
- int[] ans = new int[numCourses];
- int index = 0;
- while(!q.isEmpty())
- {
- int node = q.poll();
- ans[index++] = node;
- for(int next : adj.get(node))
- {
- indegree[next]--;
- if(indegree[next] == 0)
- q.add(next);
- }
- }
- // Cycle check
- if(index != numCourses)
- return new int[0];
- return ans;
- }
- }
RAW Paste Data
Copied
