Некая задача свелась к следующей: найти количество решений топологической сортировки.
Полный перебор подходящих перестановок не подходит, количество подходящих перестановок слишком велико (у Кнута, т.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)
It seems that counting the number of topological orderings of the graph is #P-complete. (article).
So I think that without any additional information about graph structure there is no chance to calculate an answer until the end of this era. All known algorithms are exponential, so they won't work fast on the dense graph of such great size (thousand of vertices!).
Anyway, in the article above there is a mention of algorithms that can possibly estimate the answer.
ohh :( It's not simple as I thought. Thx.
So, is 2^1000 hours acceptable?
I'm waiting my trivial O(N!) solution already :-)
I bet it requires at least 21000 bytes of memory. Only problem I can see is 1024-bit addressation.
I take it that 7 people don't have a sense of humor.
Hi if you take out printing the sequences . is possible to count the number of topological sorts?
Here is the code implementation using mask. certainly it will not help you but it works fine for smaller values.