knst's blog

By knst, 10 years ago, translation, In English

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)

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it