Created
November 8, 2021 13:56
-
-
Save ali-alaei/e7b4c2724998234ebff4524ef580ab7f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
class Solution { | |
public int[] findOrder(int numCourses, int[][] prerequisites) { | |
//A map to model the graph | |
Map<Integer, List<Integer>> adjList = new HashMap<Integer, | |
List<Integer>>(); | |
//To save the indegree of each node in the graph | |
int[] indegree = new int[numCourses]; | |
//The output or the correct sequence of courses | |
int[] topologicalOrder = new int[numCourses]; | |
//A for loop to create a graph with the map above by | |
//making adjacency lists | |
for (int i = 0; i < prerequisites.length; i++) | |
{ | |
int dest = prerequisites[i][0]; | |
int src = prerequisites[i][1]; | |
List<Integer> lst = adjList.getOrDefault(src, | |
new ArrayList<Integer>()); | |
lst.add(dest); | |
adjList.put(src, lst); | |
indegree[dest] += 1; | |
} | |
//A Queue to save nodes with indegree == 0 | |
Queue<Integer> q = new LinkedList<Integer>(); | |
for (int i = 0; i < numCourses; i++) | |
{ | |
if (indegree[i] == 0) | |
{ | |
q.add(i); | |
} | |
} | |
int i = 0; | |
//poping out the indegree == 0 nodes from the graph | |
//and store them in the output(topologicalOrder), | |
//until the queue is empty | |
while (!q.isEmpty()) | |
{ | |
int node = q.remove(); | |
topologicalOrder[i++] = node; | |
//If the graph contains the node, | |
//it updates the indegree of its neighbors | |
if (adjList.containsKey(node)) { | |
for (Integer neighbor : adjList.get(node)) | |
{ | |
//decreases the indgree of the neighbor | |
indegree[neighbor]--; | |
//If the neighboring node has no | |
//other neighbors(becomes indegree == 0), | |
//adds it to the queue | |
if (indegree[neighbor] == 0) | |
{ | |
q.add(neighbor); | |
} | |
} | |
} | |
} | |
//Returns the suitable order of the courses | |
if (i == numCourses) | |
{ | |
return topologicalOrder; | |
} | |
//If there was no suitable order, return null array | |
return new int[0]; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment