Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

public class Solution {
    public int NumBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;

        var adjList = new Dictionary<int, List<int>>();
        for (int route = 0; route < routes.Length; route++) {
            foreach (int stop in routes[route]) {
                if (!adjList.ContainsKey(stop)) {
                    adjList[stop] = new List<int>();
                }
                adjList[stop].Add(route);
            }
        }

        var q = new Queue<int>();
        var vis = new HashSet<int>();
        foreach (int route in adjList.GetValueOrDefault(source, new List<int>())) {
            q.Enqueue(route);
            vis.Add(route);
        }

        int busCount = 1;
        while (q.Count > 0) {
            int size = q.Count;
            for (int i = 0; i < size; i++) {
                int route = q.Dequeue();
                foreach (int stop in routes[route]) {
                    if (stop == target) return busCount;
                    foreach (int nextRoute in adjList.GetValueOrDefault(stop, new List<int>())) {
                        if (!vis.Contains(nextRoute)) {
                            vis.Add(nextRoute);
                            q.Enqueue(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }
}

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