133. 克隆图 [medium]

https://leetcode-cn.com/problems/clone-graph/

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}
 

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将给定节点的拷贝作为对克隆图的引用返回。

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：

输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

示例 4：

输入：adjList = [[2],[1]]
输出：[[2],[1]]

提示：

节点数不超过 100 。
每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
图是连通图，你可以从给定节点访问到所有节点。

通过次数22,298 | 提交次数39,317

Second Try

2020-06-28

bfs版本

一开始就想写bfs版本的，写了一会儿发现写不下去，直接改成DFS版本十几分钟搞定。结果看了题解，想把题解的DFS和BFS都尝试一遍，遇到几个bug，直接花去一个半钟头。可怕。。

bfs版本的要点是如果新的node不在cache中，先创建新的添加到cache中，然后再对这个新的node放到queue中进行处理。不管如何，只要遍历完成了一遍，自然就是一个新循环。

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return node

        cache = {node.val: Node(node.val)}
        start = node  
        queue = [start]
        # 其实只要遍历了一遍，在neighbors选择中每次都用新变量，则最后就是新对象。
        while len(queue):
            node = queue.pop(0)
             # 必须提前放进去，事后再放在bfs中就不行了
            # n = Node(node.val)
            # cache[n.val] = n
            n = cache[node.val] 
            for nbr in node.neighbors:
                if nbr.val not in cache:
                    nnbr = Node(nbr.val)
                    cache[nbr.val] = nnbr
                    queue.append(nbr)
                n.neighbors.append(cache[nbr.val])

        return cache[start.val]

执行用时：48 ms, 在所有 Python 提交中击败了76.29%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了100.00%的用户

bug version

一个感觉很轻松的bfs竟然写出了bug版本，调试了很久。问题是每个新的node放进去queue之前就已经在cache中存在了，结果在queue中取出的时候又创建了一个新的然后放进cache中，导致的结果就是整个图连不上来。

这个在queue中取出先创建新的node放到cache的写法是dfs中的写法，直接用过来没想到就崩溃了，浪费了很多时间。

bfs version
tmd又是一个bug写法
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return node

        cache = dict()
        start = node  
        queue = [start]
        # 其实只要遍历了一遍，在neighbors选择中每次都用新变量，则最后就是新对象。
        while len(queue):
            node = queue.pop(0)
            n = Node(node.val)
            cache[n.val] = n
            for nbr in node.neighbors:
                if nbr.val not in cache:
                    nnbr = Node(nbr.val)
                    cache[nbr.val] = nnbr
                    queue.append(nbr)
                n.neighbors.append(cache[nbr.val])

        return cache[start.val]

First Try

2020-06-28

一开始尝试BFS失败，然后直接切换到DFS，非常自然就写出来了，效果也不错。

但是在简化的时候，竟然陷入了一个无限循环的bug，问题是python的dict在get的时候，会对default value默认先进行计算。然后在这个bug上调试花了很长时间，看题解重写比直接解题花的时间多多了。

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        # node为[]的情况，分不清楚背后如何判断
        if not node:
            return node

        def dfs(node, cache):
            # print(node.val, node.neighbors)
            n = Node(node.val)
            cache[node.val] = n
            neighbors = []
            for neighbor in node.neighbors:
                if neighbor.val in cache:
                    neighbors.append(cache[neighbor.val])
                else:
                    neighbors.append(dfs(neighbor, cache))
            # 动态修改object的写法，感觉如果是其他语言可能不能这么干。。
            # 看了题解，发现差不多就是这么干的，区别在于不是直接修改neighbours,而是往node的neighbors添加元素
            n.neighbors = neighbors
            return n

        return dfs(node, {})

执行用时：48 ms, 在所有 Python 提交中击败了76.29%的用户
内存消耗：13.1 MB, 在所有 Python 提交中击败了100.00%的用户

整理写法

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return node

        cache = dict()
        def dfs(node):
            n = Node(val=node.val, neighbors=[])
            cache[n.val] = n
            for nbr in node.neighbors:
                if nbr.val in cache:
                    n.neighbors.append(cache[nbr.val])
                else:
                    n.neighbors.append(dfs(nbr))
            return n 
        return dfs(node)

bug version

一个python dict导致的无限递归bug

python dict的get操作，会预先把备用的函数进行提前计算。dict.get(x, func(x))的计算过程会直接先计算func，再来判断x是否在dict内部。

In [191]: def func(x):
     ...:     print("why print first??")
     ...:     return x
     ...:

In [192]: x = {"a": 1, "b": 2}

In [193]: x.get("a", func("a"))
why print first??
Out[193]: 1

In [194]: x.get("c", func("c"))
why print first??
Out[194]: 'c'

In [195]:

导致的结果是写出无限递归版本, 问题出在这里： n.neighbors.append(cache.get(nbr.val, dfs(nbr))), 不管cache是否有nbr.key，都会执行一遍dfs。

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return node

        cache = dict()

        def dfs(node):
            print(node.val,[nbr.val for nbr in node.neighbors], cache.keys())
            n = Node(val=node.val, neighbors=[])
            cache[n.val] = n
            for nbr in node.neighbors:
                # print("wtf",cache.keys(), nbr.val, cache.get(nbr.val))
                n.neighbors.append(cache.get(nbr.val, dfs(nbr)))
                print("check cache", node.val, cache.keys())
            return n
        
        return dfs(node)

RuntimeError: maximum recursion depth exceeded

stdout
(1, [2, 4], [])
(2, [1, 3], [1])
(1, [2, 4], [1, 2])
(2, [1, 3], [1, 2])
(1, [2, 4], [1, 2])
(2, [1, 3], [1, 2])
(1, [2, 4], [1, 2])