【深度优先搜索3】路径数量统计（邻接表存储）

图的存储

如果不会可以通过邻接表存储学习

题解

题目描述

题目描述：

给定一张有向无环图，图中的节点编号从 $1$ 到 $n$。图的边是有向的，每条边由一个起点和终点组成。在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。 图的存储方式采用邻接表，即对于每个节点 $u$，它的所有出边存储在一个列表中。请你求出从节点 $s$ 到节点 $t$ 之间有多少条不同的路径。

输入：

第一行输入两个整数 $n$ 和 $m$（$2 \leq n \leq 30, 1 \leq m \leq 120$），分别表示图中节点的数量和边的数量。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示从节点 $u$ 到节点 $v$ 有一条有向边。

最后一行输入两个整数 $s$ 和 $t$（$1 \leq s, t \leq n$），表示起点和终点。

输出：

输出一个整数，表示从节点 $s$ 到节点 $t$ 之间的不同路径数。如果没有这样的路径，则输出 $0$。

样例输入：

4 4
1 2
1 3
2 4
3 4
1 4

样例输出：

2

提示：

• 对于样例输入，存在两条从节点 $1$ 到节点 $4$ 的路径：$1 \rightarrow 2 \rightarrow 4$ 和 $1 \rightarrow 3 \rightarrow 4$。
• 图是无环图，因此不存在自环或环路。