Студент 2-го курса, учащийся на направлении "Информационные системы и технологии".
Контакты
Местоположение
Россия, Пермский край, Пермь

Достижения

Все достижения (1)

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

Все теги (11)

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

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

    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 комментария

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

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