Некая задача свелась к следующей: найти количество решений топологической сортировки.

Полный перебор подходящих перестановок не подходит, количество подходящих перестановок слишком велико (у Кнута, т.4 есть способ генерации всех решений топологической сортировки).

Сами решения не нужны.

Ограничение на количество вершин N: 10^3, ограничение на количество дуг M: 3 * 10^5. Циклов гарантированно нет. Время работы алгоритма — разумное. 1 секунда — великолепно, минута — хорошо, час — удовлетворительно, неделя — плохо, но приемлимо: это лучше перебора :)

Может кто-нибудь подсказать с решением или в какую сторону копать?

Тривиальный пример:
N = 6; M = 7
V: 1 2 3 4 5
E:
1 2
1 3
1 4 
1 5
2 4
2 5
3 5

Ответ:
5
(1 2 3 4 5)
(1 3 2 4 5)
(1 2 4 3 5)
(1 2 3 5 4)
(1 3 2 5 4)