I am practising on a task to find all topological sorts of a DAG
(input is given eg
1 4 5
1st line: there is an edge from 1 to 4 and also an edge from 4 to 5.
2nd line: there is an edge from 3 to 4
3rd line: there is an edge from 2 to 1
The question is how many different topsorts exist.
(biggest number in input is the number of nodes).
i tried solving this using depth first search but it turned out to be kind of slow for big inputs. any good ideas?
(the dfs i did was having adjacency list of all nodes and for all nodes with an empty adjacency list(or adjacency list that had only visited nodes) where added to the topsort and marked as visited.)
Thanks in advance