Сложность: 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 {
var seen = Set<Int>()
let MAX_EDGE_VAL = 1000
func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
var graph = Array(repeating: [Int](), count: MAX_EDGE_VAL + 1)
for edge in edges {
seen.removeAll()
if !graph[edge[0]].isEmpty && !graph[edge[1]].isEmpty && dfs(graph, edge[0], edge[1]) {
return edge
}
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
}
return []
}
func dfs(_ graph: [[Int]], _ source: Int, _ target: Int) -> Bool {
if !seen.contains(source) {
seen.insert(source)
if source == target { return true }
for nei in graph[source] {
if dfs(graph, nei, target) { return true }
}
}
return false
}
}Ставь 👍 и забирай 📚 Базу знаний