Изменения

Будем проверять множества переходов для двух вершин. Запустим [[Обход в глубину, цвета вершин | обход в глубину]] из стартовых вершин, если множество переходов по ребрам для двух вершин совпадают и также это выполнено для вершин соответствующим концам ребер (если у нас соответствующие вершины дьявольские, то множество переходов считаем равными) то два автомата изоморфны. Заметим, что если мы рассмотрим два автомата состоящих из пройденных вершин, то эти два автомата будут изоморфны (из этого следует, что на когда мы обойдем все вершины, это тоже будет выполнено). Этот алгоритм пройдет по всем вершинам и ребрам ровно один раз, из этого следует время работы <tex>O(N + M) </tex>, где <tex> N</tex> {{---}} суммарное число вершин в автоматах, <tex> M</tex> {{---}} суммарное число ребер.