Java Solution using Topological sorting a DAG (10ms)


  • 0
    H

    According to Wiki(https://en.wikipedia.org/wiki/Topological_sorting)
    alt text
    L ← Empty list that will contain the sorted elements
    S ← Set of all nodes with no incoming edges
    while S is non-empty do

      remove a node n from S
      add n to tail of L
      for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
          insert m into S
    if graph has edges then
      return error (graph has at least one cycle)
    else
      return L (a topologically sorted order)

    I have my code as shown below:

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] qualifiedList = new List[numCourses];
        int[] incomingEdges = new int[numCourses];
        for(int i=0;i<qualifiedList.length;i++){
            qualifiedList[i] = new LinkedList<Integer>();
        }
        for(int[] pair:prerequisites){
            qualifiedList[pair[1]].add(pair[0]);
            incomingEdges[pair[0]]++;
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i=0;i<incomingEdges.length;i++){
            if(incomingEdges[i]==0)
                queue.add(i);
        }
        int edgeCnt = prerequisites.length;
        int[] res = new int[numCourses];
        int idx = 0;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            res[idx] = cur;
            idx++;
            for(int qualifiedCrs: qualifiedList[cur]){
                edgeCnt--;
                if(--incomingEdges[qualifiedCrs]==0){
                    queue.add(qualifiedCrs);
                }
            }
        }
        if(edgeCnt==0){
            return res;
        }
        return new int[0];
    }
    

    This method can be used in both Course Schedule II and Course Schedule


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.