Блог пользователя Temirulan

Поиск конденсации графа
Автор Temirulan, 10 лет назад, По-русски

Наткнулся на задачу с lightoj.com. В общем-то надо было найти конденсацию графа. Как я знаю находится двумя DFS-ами. Сперва по нормальному графу, а затем по инвертированному или же сперва по инвертированному, а затем по нормальному графы. Так вот эти 2 кода получают 2 разных вердикта. Помогите и объясните пожалуйста.
Код получивший Accepted, время работы 0,9с.
Код получивший TLE, не укладывается в 5с.

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 6   Проголосовать: нравится +26 Проголосовать: не нравится

я твой ТЛ код сделал АС code

Может это поможет:

По-моэму, когда строишь граф для паросочетание, у тебя получиться один и тот же граф, но порядок в векторе разные (то есть обход по-разному делается). Из-за этого иногда Куна быстро работает, иногда нет.

→ Ответить