408相关算法刷题【图论】

LeetCode 133. 克隆图

题目类型

1. 深拷贝
2. dfs

题目链接

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

思路

1. 由于是无向边，使用哈希表(原图，克隆图)避免dfs的时候产生回路，死循环
2. 写一个dfs函数，遍历所有点并把点加入哈希表
3. 接着遍历所有点

AC代码

class Solution {
public:
    // (原图的结点，克隆图的结点)
    unordered_map<Node*, Node*> visited;
    Node* cloneGraph(Node* node) &#123;
        if (!node) return NULL;
        // 复制所有点
        dfs(node);

        // 复制边
        for (auto [s, d] : visited)
        &#123;
            // 原图点s的邻点集ver 放入克隆图的点d的邻点集中
            for (auto ver : s->neighbors)
            &#123;
                d->neighbors.push_back(visited[ver]);
            &#125;
        &#125;
        return visited[node];
    &#125;
    void dfs(Node* node)
    &#123;
        // 复制结点
        visited[node] = new Node(node->val);

        // 遍历该点的所有邻点
        for (auto ver : node->neighbors)
        &#123;
            if (visited.count(ver) == 0) dfs(ver);
        &#125;
    &#125;
&#125;;

##

题目类型

1. 题目链接

思路

AC代码

##【未完待更】