题目描述:
给定一张有向无环图,图中的节点编号从 1 到 n。图的边是有向的,每条边由一个起点和终点组成。在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。 图的存储方式采用邻接表,即对于每个节点 u,它的所有出边存储在一个列表中。请你求出从节点 s 到节点 t 之间有多少条不同的路径。
输入:
第一行输入两个整数 n 和 m(2≤n≤30,1≤m≤120),分别表示图中节点的数量和边的数量。
接下来 m 行,每行包含两个整数 u 和 v(1≤u,v≤n),表示从节点 u 到节点 v 有一条有向边。
最后一行输入两个整数 s 和 t(1≤s,t≤n),表示起点和终点。
输出:
输出一个整数,表示从节点 s 到节点 t 之间的不同路径数。如果没有这样的路径,则输出 0。
样例输入:
4 4
1 2
1 3
2 4
3 4
1 4
样例输出:
2
提示:
如果不会可以通过邻接表存储学习
给定一张有向无环图(DAG),节点编号从 1
到 n
,每条边由一个起点和终点组成,采用邻接表存储。求从指定起点 s
到指定终点 t
的路径总数。
n
和边数 m
。g
存储图。from collections import defaultdict
def main():
# 读取节点数和边数
n, m = map(int, input().split())
# 初始化邻接表
g = {i: [] for i in range(1,n+1)}
# 读取边的信息并构建邻接表
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
s
和终点 t
。 # 读取起点s和终点t
s, t = map(int, input().split())
dfs(u)
,计算从当前节点 u
到终点 t
的路径数。1
。u
出发的所有邻接节点,递归调用 dfs(v)
,并累加路径数。 def dfs(u):
"""
递归函数,计算从节点u到终点t的路径数
"""
# 如果到达终点t,说明找到了一条路径
if u == t:
return 1
# 初始化路径数量
res = 0
# 遍历所有邻接节点并递归计算
for v in g[u]:
res += dfs(v)
return res
dfs(s)
从起点 s
开始计算路径总数。ans
,并输出。 # 调用dfs从起点s开始计算路径数量
ans = dfs(s)
# 输出路径数量
print(ans)
将上述步骤汇总,得到以下完整代码:
from collections import defaultdict
def main():
# 读取节点数和边数
n, m = map(int, input().split())
# 初始化邻接表
g = defaultdict(list)
# 读取边的信息并构建邻接表
for _ in range(m):
u, v = map(int, input().split())
g[u].append(v)
# 读取起点s和终点t
s, t = map(int, input().split())
def dfs(u):
"""
递归函数,计算从节点u到终点t的路径数
"""
# 如果到达终点t,说明找到了一条路径
if u == t:
return 1
# 初始化路径数量
res = 0
# 遍历所有邻接节点并递归计算
for v in g[u]:
res += dfs(v)
return res
# 调用dfs从起点s开始计算路径数量
ans = dfs(s)
# 输出路径数量
print(ans)
if __name__ == '__main__':
main()