Javascript DFS topological sort beats 100% runtime


  • 0
    W
    var findOrder = function(numCourses, prerequisites) {
        var res = [];
        if (numCourses == 0) return res;
        var pending = {};
        var completed = {};
        var G = new Array(numCourses);
        for (var i=0; i<numCourses; i++) {
            G[i] = [];
        }
        // init G
        var E = prerequisites.length;
        for (var i=0; i< E; i++) {
            var pair = prerequisites[i];
            G[pair[0]].push(pair[1]);
        }
        
        for (i=0; i<numCourses; i++) {
            if (!completed[i]) {
                if(!DFS(G, pending, completed, res, i)) {
                    return [];
                }
            }
        }
        return res;
    };
    
    var DFS = function(G, pending, completed, res, v) {
        if (completed[v]) return true;
        if (pending[v]) return false;
        pending[v] = true;
        var len = G[v].length;
        for (var i=0; i<len; i++) {
            if(!DFS(G, pending, completed, res, G[v][i])) return false;
        }
        delete pending[v];
        completed[v] = true;
        res.push(v);
        return true;
    };
    

Log in to reply
 

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