Задать вопрос
YaKotikTvoy

YaKotikTvoy

Стьюдик
Информация
Контакты

Достижения

Все достижения (2)
1
Хороший вопрос
На вопрос подписалось 3 человека за сутки
1
Хороший вопрос
На вопрос подписалось 5 человек за сутки

Наибольший вклад в теги

Все теги (13)

Лучшие ответы пользователя

Все ответы (6)

  • Как решить олимпиадную задачу с графами?

    YaKotikTvoy
    @YaKotikTvoy
    Стьюдик
    Здесь вам нужно найти остовное дерево графа, да притом такое, что его можно выпрямить. Но так как, там по сути, как я понял, просто цикл, а ещё есть одно тупиковое ответвление, то вам просто нужно взять и запустить DFS, либо BFS алгоритм с точки, которая около черенка.
    Для того, чтобы BFS или DFS сразу не пошли к черенку, удалите ребро ведущую к выходу, то есть тупику, но при этом подразумеваете, что оно есть , это уже и будет то минимальное расстояние, остовное дерево.
    Запишите этот путь в массив или множество и задача решена.
    6282ce27c8710274314724.png
    Вот DFS, припишите то, что нужно для записи пути и выведите его.
    N,M = [int(i) for i in input().split()]
G = {}
for i in V:
    if i not in used:
            t += 1
            dfs(i,G,used)

    N, M - количество вершин и ребер соответственно.
    Все ребра и вершины необходимо прописать самому.
    В данном случае, лучше DFS (поиск в глубину).
    Ответ написан
    4 комментария
    4 комментария

Лучшие вопросы пользователя

Все вопросы (50)