1006题解法

gistfile1.js

function solve(modules){

  function getBranch(node, tree){
    var ret = [];
    var current = node;
    do{
      ret.push(current);
    }while(current = tree[current])
    return ret;
  }

  var tree = {};  //tree是一个包含单parent的树
  var count = 0;
  var solved = {};

  function solveRequire(node, tree){
    if(solved[node]) return;
    solved[node] = true;

    var requires = modules[node];

    if(!(node in tree)){
      tree[node] = null;
    }

    for(var j = 0; j <requires.length; j++){
      var requireNode = requires[j];
      //console.log(node, requireNode, JSON.stringify(tree));

      solveRequire(requireNode, tree); //先处理依赖节点

      if(!tree[node]){
        //当前节点在树根上
        tree[node] = requireNode;

      }else{
        //node 和 requireNode 都在树上， 判断他们的祖先那一枝
        var branchNode = getBranch(node, tree);
        var branchReqNode = getBranch(requireNode, tree);
        
        if(branchReqNode.indexOf(node) >= 0){
          //循环依赖
          //console.log(node, requireNode, tree)
          return [];
        }
        if(branchNode.indexOf(requireNode) >= 0){
          //关系已经正确了，什么都不要做，继续
          continue;
        }
        var found = false;
        for(var k = 1; k < branchReqNode.length; k++){
          //往上找公共祖先
          var idx = branchNode.indexOf(branchReqNode[k]);
          if(idx >= 0){
            //找到了公共祖先，将公共祖先的儿子的父亲变成requireNode
            tree[branchNode[idx - 1]] = branchReqNode[k - 1];
            found = true;
            break;
          }
        }
        if(!found){
          //貌似木有公共祖先
          tree[branchNode[branchNode.length - 1]] = branchReqNode[k - 1];
        }
        ///结束
      }
    }    
  }

  for(var node in modules){
    count++;
    solveRequire(node, tree);
  }
  
  //console.log(JSON.stringify(tree));
  var ret = [], i = 0;
  while(ret.length < count && i++ < 1000){
    for(var node in tree){
      if(tree[node] == null || ret.indexOf(tree[node]) >= 0){
        ret.push(node);
        delete tree[node];
      }
    }
  }
  return ret;
}