Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

[Help] How to solve this DAG problem?

Revision en1, by SmolBrain, 2022-04-25 16:05:18

Problem Link

Abridged problem statement: Count the total number of distinct topological orderings of a DAG (Directed Acyclic Graph), given that each node has at most 1 incoming edge

My approach: Find an arbitrary topological ordering of the DAG using dfs and use dp to find the answer. However, I'm unable to formulate the dp states correctly.

I've hunted the entire internet for this problem's solution, but couldn't find it, so the CF community is my only hope! Please provide some hints to solve this problem.

Thanks :D

Tags help, dag, toposort, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SmolBrain 2022-04-25 16:05:18 610 Initial revision (published)