Изменить порядок маршрутов с помощью Python

Переупорядочить маршруты, чтобы все пути вели к нулевому городу, — популярный вопрос на собеседованиях по программированию. В этой задаче вам нужно переупорядочить соединения между городами так, чтобы все пути вели в город, помеченный как ноль. Итак, если вы хотите узнать, как изменить порядок маршрутов с помощью Python, эта статья для вас. В этой статье я расскажу вам, как изменить порядок маршрутов, чтобы все пути вели к нулевому городу с помощью Python.

Изменить порядок маршрутов, чтобы все пути вели к нулевому городу

В задаче о переупорядочивании маршрутов так, чтобы все пути вели к нулевому городу, вам будет задан массив связей между городами в парах целых чисел. Каждое соединение будет показывать односторонний маршрут из одного города в другой. Например, [1, 0] означает, что существует дорога с односторонним движением из города 1 в город 0. Ваша задача состоит в том, чтобы переупорядочить соединения таким образом, чтобы в каждый город можно было добраться из города 0 прямо или косвенно. Выходное значение должно возвращать минимальное количество измененных ребер.

Вот пример входных и выходных значений этой задачи:

• Вход: n = 5, связи = [[1,0],[1,2],[3,2],[3,4]]| Выход = 2

В приведенном выше примере выход равен 2, потому что нам нужно поменять местами два соединения, чтобы все пути вели к нулевому городу.

Изменение порядка маршрутов с помощью Python

Надеюсь, вы поняли, что означает проблема переупорядочивания маршрутов, чтобы все пути вели в нулевой город. Теперь вот как изменить порядок маршрутов с помощью Python:

from collections import defaultdict
def minReorder(n, connections):
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append((v, 1))
        graph[v].append((u, 0))
            
    def dfs(node):
        nonlocal total
        visited.add(node)
            
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                total += cost
                dfs(neighbor)
    total = 0
    visited = set()
    dfs(0)
    return total

n = 6
connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
print(minReorder(n, connections))

Output: 3

Ниже показано, как работает приведенный выше код:

1. Мы начали с создания графа, показывающего все подключенные маршруты. Затем он проходит по каждому маршруту и ​​проверяет, является ли он односторонним или нет.
2. Если маршрут односторонний, мы добавили к нему «стоимость», чтобы указать, что его необходимо изменить. Эта «стоимость» отслеживает, сколько путей необходимо изменить.
3. Наконец, мы использовали поиск в глубину алгоритм, чтобы пройти все маршруты и найти, сколько нужно переупорядочить.
4. Затем он возвращает общее количество переупорядоченных маршрутов.

Вот как вы можете изменить порядок маршрутов с помощью Python. Вы можете найти еще много практических вопросов для собеседований по программированию, решенных и объясненных с использованием Python. здесь.

Краткое содержание

Переупорядочить маршруты, чтобы все пути вели к нулевому городу, — популярный вопрос на собеседованиях по программированию. В этой задаче вам нужно переупорядочить соединения между городами так, чтобы все пути вели в город, помеченный как ноль. Надеюсь, вам понравилась эта статья о том, как изменить порядок маршрутов с помощью Python. Не стесняйтесь задавать ценные вопросы в разделе комментариев ниже.