Java solution. topological sort.


  • 0
    Z
    public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // transform.
        boolean[][] g = new boolean[numCourses][numCourses];
        for(int[] e : prerequisites)
            g[e[1]][e[0]] = true;
            
        /*compute answer*/    
        Deque<Integer> topo = new LinkedList<>();
        // detect cycle, fill topological order at the same time
        if(directed_cycle(numCourses, g, topo))
            return new int[0];
            
        int[] ret = new int[topo.size()];
        int idx =0;
        for(int v: topo)
            ret[idx++] = v;
                    
        return ret;
    }
    
    static int NOT_VISITED = 0;
    static int CUR_VISITE = 1;
    static int VISITED = 2;
    
    // has cycle?
    boolean directed_cycle(int vcount , boolean[][] g, Deque<Integer> topo){
        int[] stat = new int[vcount];
        
        for(int node =0; node < vcount ; node ++){
            if(stat[node] == NOT_VISITED && hasCycle(g,stat,node,topo))
                return true;
        }
        
        return false;
    }
    
    // true if cycle found
    boolean hasCycle(boolean[][] g, int[] stat, int node, Deque<Integer> topo){
        if(stat[node] == CUR_VISITE)
            return true;
        if(stat[node] == VISITED)
            return false;
            
        stat[node] = CUR_VISITE;
        boolean ret = false;
        for(int end = 0; end < g[node].length; end ++){
            if(g[node][end] && hasCycle(g,stat,end,topo)){
                ret =  true;
                break;
            }
        }
        
        topo.addFirst(node);
        stat[node] = VISITED;
        return ret;
    }
    

    }


Log in to reply
 

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