dfs+哈希表+圖

先深搜建立所有點，加入哈希表。再遍歷哈希表，按照拷貝前后的結點，拷貝邊。最后返回某一結點，即為所求。

成都創新互聯電話聯系：18980820575，為您提供成都網站建設網頁設計及定制高端網站建設服務，成都創新互聯網頁制作領域10年，包括除甲醛等多個方面擁有豐富的網站維護經驗，選擇成都創新互聯，為網站保駕護航！

class Solution {public:
    unordered_mapmp;
    Node* cloneGraph(Node* node) {if(!node) return node;
        dfs(node);
        for(auto &[s,d]:mp)
            for(auto &e:s->neighbors)
                d->neighbors.push_back(mp[e]);
        return mp[node];
    }
    void dfs(Node *node) {mp[node] = new Node(node->val);
        for(auto &v:node->neighbors)
            if(!mp.count(v)) dfs(v);
    }
};

1. 時間復雜度 : O ( ∑ i = 0 n m i ) O(\sum_{i=0}^{n} m_i) O(∑i=0n?mi?) ， n n n 是點的數量， m m m 是邊的數量，遍歷所有點的所有邊，時間復雜度 O ( ∑ i = 0 n m i ) O(\sum_{i=0}^{n} m_i) O(∑i=0n?mi?) 。
2. 空間復雜度 : O ( n ) O(n) O(n) ， 哈希表存 n n n 個點的空間復雜度 O ( n ) O(n) O(n) 。

AC

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站標題：力扣(LeetCode)133.克隆圖(C++)-創新互聯
網頁地址：http://vcdvsql.cn/article10/epcgo.html

成都網站建設公司_創新互聯，為您提供企業建站、微信小程序、網站改版、App開發、動態網站、域名注冊

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯