算法1

(bfs) $O(n^2)$

这个题最大的难点，个人觉得就是图遍历的难点，当遍历邻居节点时会把原来遍历过的节点再次入队，这就是个没完没了的事情了，重点就是把遍历的节点标出来，不要让它在入队了

时间复杂度

参考文献

java 代码

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return null;
        Map<Node,Node> flag = new HashMap<>();//我们将节点和它的克隆节点放在一起，当做标志位
        return dfs(node,flag);
    }
    public Node dfs(Node node,Map<Node,Node> flag){
        if(flag.containsKey(node)) return flag.get(node);//如果这个节点在flag中，表示已经被遍历处理了，存进去了它的克隆节点了
        Node clone = new Node(node.val,new ArrayList<>());//否则的话，就克隆这个节点;
        flag.put(node,clone);//并把节点加到标志中去,就是为了遍历到邻居节点的时候，被克隆的节点不在继续，所以标志位一定要比遍历邻居要早
        for(Node n :node.neighbors){//然后把node节点的邻居节点的克隆加到本节点的克隆中去
            clone.neighbors.add(dfs(n,flag));
        }
        //表示这个节点建立完毕
        return clone;

    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla