Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium

Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.

Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.

Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

👨‍💻 Алгоритм:

1⃣Создание структуры данных и инициализация:
Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла.
Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла.
Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета.

2⃣Инициализация очереди и начальных условий:
Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра).
Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно.

3⃣Обработка очереди и обновление результата:
Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра).
Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь.

😎 Решение:

class Solution {
    func shortestAlternatingPaths(_ n: Int, _ redEdges: [[Int]], _ blueEdges: [[Int]]) -> [Int] {
        var adj = [Int: [[Int]]]()
        for redEdge in redEdges {
            adj[redEdge[0], default: []].append([redEdge[1], 0])
        }
        for blueEdge in blueEdges {
            adj[blueEdge[0], default: []].append([blueEdge[1], 1])
        }
        
        var answer = [Int](repeating: -1, count: n)
        var visit = Array(repeating: [false, false], count: n)
        var queue = [(0, 0, -1)]
        answer[0] = 0
        visit[0][0] = true
        visit[0][1] = true
        
        while !queue.isEmpty {
            let (node, steps, prevColor) = queue.removeFirst()
            
            if let neighbors = adj[node] {
                for neighbor in neighbors {
                    let nextNode = neighbor[0]
                    let color = neighbor[1]
                    if !visit[nextNode][color] && color != prevColor {
                        if answer[nextNode] == -1 {
                            answer[nextNode] = steps + 1
                        }
                        visit[nextNode][color] = true
                        queue.append((nextNode, steps + 1, color))
                    }
                }
            }
        }
        return answer
    }
}

Ставь 👍 и забирай 📚 Базу знаний