How to calculate number of topological sort?
Brute force not acceptable: number of vertex N is 10^3; number of edges M: 3 * 10^5. Time limit of calculation isn't critical: 1 hour is acceptable. Can you help me with this problem? I can't find solution.
Trivial example:
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
Answer:
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.