🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 684. Redundant Connection
Сложность: 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⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.
😎 Решение:
package main
func findRedundantConnection(edges [][]int) []int {
const MAX_EDGE_VAL = 1000
graph := make([][]int, MAX_EDGE_VAL+1)
for i := range graph {
graph[i] = make([]int, 0)
}
seen := make(map[int]bool)
var dfs func(source, target int) bool
dfs = func(source, target int) bool {
if !seen[source] {
seen[source] = true
if source == target {
return true
}
for _, nei := range graph[source] {
if dfs(nei, target) {
return true
}
}
}
return false
}
for _, edge := range edges {
seen = make(map[int]bool)
if len(graph[edge[0]]) > 0 && len(graph[edge[1]]) > 0 && dfs(edge[0], edge[1]) {
return edge
}
graph[edge[0]] = append(graph[edge[0]], edge[1])
graph[edge[1]] = append(graph[edge[1]], edge[0])
}
return nil
}
Ставь 👍 и забирай 📚 Базу знаний
