Дана ссылка на узел в связном неориентированном графе.
Вернуть глубокую копию (клон) графика.
Каждый узел в графе содержит значение (int
) и список (List[Node]
) своих соседей.
class Node { public int val; public List<Node> neighbors; }
Формат тестового примера:
Для простоты значение каждого узла совпадает с индексом узла (с индексом 1). Например, первый узел с val == 1
, второй узел с val == 2
и так далее. Граф представлен в тестовом примере с помощью списка смежности.
Список смежности – это набор неупорядоченных списков, используемых для представления конечного графа. Каждый список описывает множество соседей узла в графе.
Данный узел всегда будет первым узлом с val = 1
. Вы должны вернуть копию данного узла в качестве ссылки на клонированный граф.
Пример 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).
Пример 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.
Пример 3:
Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.
Ограничения:
- Количество узлов в графе находится в диапазоне
[0, 100]
. 1 <= Node.val <= 100
Node.val
уникален для каждого узла.- В графе нет повторяющихся ребер и нет петель.
- Граф подключен, и все узлы можно посетить, начиная с данного узла.
Решение
Временная сложность O(v+e)
Пространственная сложность O(3n) -›O(n)
Вы видите эту зеленую кнопку подписки? 🐌