Сложность: medium
В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.
Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.
Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
👨💻 Алгоритм:
1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.
2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся.
3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.
😎 Решение:
class Solution:
def __init__(self):
self.seen = set()
self.MAX_EDGE_VAL = 1000
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
graph = [[] for _ in range(self.MAX_EDGE_VAL + 1)]
for edge in edges:
self.seen.clear()
if graph[edge[0]] and graph[edge[1]] and self.dfs(graph, edge[0], edge[1]):
return edge
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
return []
def dfs(self, graph: List[List[int]], source: int, target: int) -> bool:
if source not in self.seen:
self.seen.add(source)
if source == target:
return True
for nei in graph[source]:
if self.dfs(graph, nei, target):
return True
return False
Ставь 👍 и забирай 📚 Базу знаний