SmolBrain's blog

By SmolBrain, history, 2 years ago, In English

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

Full text and comments »

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