Last Updated on 2022-02-23 by Clay
題目
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.
Constraints:
- The number of nodes in the graph is in the range
[0, 100]. 1 <= Node.val <= 100Node.valis unique for each node.- There are no repeated edges and no self-loops in the graph.
- The Graph is connected and all nodes can be visited starting from the given node.
題目給定一個輸入的節點，該節點處在一個無向連接圖中。我們要做的，就是把整張圖複製起來（deep copy），然後回傳我們複製好的開始節點。
解題思路
這題我一開始就想到了使用 DFS 的方式去展開所有節點...... 但很慚愧地沒有注意到節點之間相鄰連結的節點其實會包含重複的節點...... 也就是說可能是會包含我們當前正在偵測的節點。
第一次碰到這個題目，一開始直接給寫成了無窮迴圈。慚愧。
直到看了討論區後，這才意識到可以使用 hash table 把跑過的節點紀錄起來。（題目給的前提之一，就是每個值都只會出現一次）
C++ 範例程式碼
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/
class Solution {
public:
Node* dfs(Node* node, unordered_map<int, Node*>& visited) {
// Create a new Node
Node* cloneNode = new Node(node->val);
// Record the node is visited
visited.insert({node->val, cloneNode});
// Keep finding
for (Node* neighbor: node->neighbors) {
if (visited.count(neighbor->val)) {
cloneNode->neighbors.push_back(visited[neighbor->val]);
}
else {
// DFS
Node* newCloneNode = dfs(neighbor, visited);
cloneNode->neighbors.push_back(newCloneNode);
}
}
return cloneNode;
}
Node* cloneGraph(Node* node) {
// Base case
if (node == nullptr) return nullptr;
// Init
unordered_map<int, Node*> visited;
// Clone
return dfs(node, visited);
}
};Python 範例程式碼
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def dfs(self, node, visited):
# Create a new Node
cloneNode = Node(node.val)
# Record the node is visited
visited[node.val] = cloneNode
# Keep finding
for neighbor in node.neighbors:
if neighbor.val in visited:
cloneNode.neighbors.append(visited[neighbor.val])
else:
newCloneNode = self.dfs(neighbor, visited)
cloneNode.neighbors.append(newCloneNode)
return cloneNode
def cloneGraph(self, node: 'Node') -> 'Node':
# Base case
if not node: return node
# Init
visited = {}
# Clone
return self.dfs(node, visited)