Сложность: medium
Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие.
Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi.
В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город.
Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог.
Гарантируется, что каждый город может добраться до города 0 после перенаправления.
Пример:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
👨💻 Алгоритм:
1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное).
2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1.
3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count.
😎 Решение:
class Solution {
var count = 0
func dfs(_ node: Int, _ parent: Int, _ adj: [Int: [[Int]]]) {
guard let neighbors = adj[node] else { return }
for neighbor in neighbors {
let (nei, sign) = (neighbor[0], neighbor[1])
if nei != parent {
count += sign
dfs(nei, node, adj)
}
}
}
func minReorder(_ n: Int, _ connections: [[Int]]) -> Int {
var adj = [Int: [[Int]]]()
for connection in connections {
adj[connection[0], default: []].append([connection[1], 1])
adj[connection[1], default: []].append([connection[0], 0])
}
dfs(0, -1, adj)
return count
}
}Ставь 👍 и забирай 📚 Базу знаний