Lexi's Leetcode solutions

Posts Tagged ‘graph

给一个Set<Node>,每个节点里面有个List<Node> children,求它的sorted list representation http://en.wikipedia.org/wiki/Topological_sorting。Google phone就挂这了。

比如下图,假设箭头全是向下的,则return list就是A->C->E->F->B->D,就是其中一个valid solution。所有dependent关系都满足,然后那些无dependent关系的(比如B和C, D和E就任意顺序就行)。

  A
/   \
B   C
\   /\
  D   E -> F

算法:

  1. 一个map<Node, Boolean>记录走过的节点,false表示visiting (gray), true表示visited (black),无环图说明不会遇见灰色节点(一个节点还没visit完呢就又遇见它了),否则就是有环了(circular dependent)。
  2. 每次从白色节点(set里)里挑一个,从它开始DFS。
  3. DFS就是把这个节点涂灰,然后顺次DFS它的孩子,每个先visited的孩子的list都插在dummy head的最前面,所以老二的孙子其实排在老大前面(比如C的老大是D,老二是E->F,结果就是CEFD(最后把父亲放最前面)。这样保证每个孩子序列都是原来顺序,各个孩子树之间反正没关系,就顺次排开就行了。
  4. 每次一个节点被涂黑,就从set里remove。直到set空了为止。
Node topoSort(Set<Node> set) {
    Map<Node, Boolean> map = new HashMap<Node, Boolean>;
    Node dummy = new Node();
    while (!set.isEmpty()) {
        Node node = set.iterator().next();
        dfs(node, dummy, set, map);
    }
    return dummy.next();
} 
void dfs(Node node, Node dummy, Set<Node> unBlacked, Map<Node, Boolean> map) {
    if (!map.containsKey(node)) {
        map.put(node, false);
        for (Node child : node.children) {     
            dfs(child, dummy, set, map);
        }
        Node break = dummy.next;
        dummy.next = node;
        node.next = break;
        map.put(node, true);//mark black
        set.remove(node);
     } else if (map.get(node) == false) {
        //gray, there's a loop
        throw new LoopExistException(); 
}
Advertisements
Tags: ,

倒是20分钟写出来了bugfree,比较喜欢这种利用data structure的题,感觉试一试总能想出来。

这个题就是基本BFS,要点是生成新节点的同时,怎么把新节点和其他新节点连起来呢?这就需要一个新旧节点对应map,每次生成新节点A’,要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’,因为下次把A当作root的时候,还会经历B作为child,这时再A’->B’。

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
  if (node == null)
    return null;
  Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); 
  Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
  enqueueAndClone(q, node, map);
  while (!q.isEmpty()) {
    UndirectedGraphNode parent = q.poll();
    for (UndirectedGraphNode child : parent.neighbors) {
      if (!map.containsKey(child))
        enqueueAndClone(q, child, map);
      map.get(parent).neighbors.add(map.get(child));//不管是否visit过,都要单向连接 
    }
  }
  return map.get(node);
}
private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
  q.add(node);
  UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
  map.put(node, newNode);
}