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)