Я пытаюсь лучше понять структуры данных и алгоритмы, поэтому я пытаюсь решить эту проблему: https://maps20.kattis.com/problems/maps20.roundtrips
Я использовал BFS и проверил, есть ли был путь между вершины источника и вершины назначения. Так как вершины пронумерованы 0, 1, ..., n-1, я пробегаю 2 цикла и проверяю каждую возможную пару вершин и запускаю BFS на этих вершинах. Если пути не существует, я увеличиваю переменную счетчика.
Я видел этот пост: Как определить, приводит ли добавление ребра к ориентированному графу к циклу?
Это очень помогло, но я получаю сообщение об ошибке по времени. Это похоже на очень медленный способ определения количества возможных ребер без создания нового цикла. Есть ли простой способ ускорить этот процесс, которого я не вижу?