В общем случае, чтобы найти все циклы длины n надо подсчитать
Tr(A^n)/n. A - матрица смежности. Tr() - это след (сумма элементов на диаганали). Т.е. возводите матрицу смежности из 0 и 1 в степень n и суммируете элементы по диагонали. Делить на n надо, потому что тут циклы считаются ориентированными и упорядочеными. Т.е. A->B->C посдчитается отдельно от B->C->A. Если граф неориентированный, то надо будет дополнительно поделить на 2 в конце.
Важно, тут будут считаться циклы, ходящие по одним и тем же вершинам и ребрам. Но для n=3 это не важно, если только у вас петель в графе нет.
Для n=3 можно чуть быстрее - возвести матрицу в квадрат и получить матрицу количеств путей длины 2. Потом можно пройтись по всем ребрам и просуммировать все циклы с этим ребром (известное уже количество путей длины 2 между двумя концами ребра). Тут как бы последнее, третье умножение пропускается и вместо него считаются только элементы на диагонали. Потом надо будет поделить на 3, потому что тут вы считаете каждый цикл 3 раза.
Можно воспользоваться быстрым умножением матриц
Штрессена или присобачить какое-нибудь битовое сжатие, как я уже советовал вам в
этом вопросе.
В зависимости от размерности матрицы (количества вершин) битовое сжатие может быть быстрее Штрассена или какого-либо другого быстрого алгоиртма умножения матриц.
Простой
