A6194. 徒競走
编程题
普及+/提高
知识点
题目描述
给定一个有向无环图（DAG），请计算该图的拓扑排序方案数。
输入格式
第一行包含两个整数 $N$ 和 $M$，分别表示顶点数和边数。
接下来的 $M$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从顶点 $x$ 指向顶点 $y$ 的有向边。
接下来的 $M$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从顶点 $x$ 指向顶点 $y$ 的有向边。
输出格式
输出一个整数，表示该有向无环图的拓扑排序方案数。
输入输出样例
输入 #1
3 2 2 1 2 3
输出 #1
2
输入 #2
5 5 1 2 2 3 3 5 1 4 4 5
输出 #2
3
输入 #3
16 1 1 2
输出 #3
10461394944000
说明/提示
- $1 \leq N \leq 16$
- $0 \leq M \leq N(N-1)/2$
- $1 \leq x, y \leq N$
- 输入保证图是有向无环图（DAG）。
- $0 \leq M \leq N(N-1)/2$
- $1 \leq x, y \leq N$
- 输入保证图是有向无环图（DAG）。