dfs真的要好好学

解题思路:

注意事项:

参考代码:

#输入站点数和通道数
n,m=map(int,input().split())
#定义图的邻接矩阵
table=[[0]*(n) for _ in range(n)]
#定义是否访问过改节点的矩阵（是为True）
flag=[False for _ in range(n)]
#将图中相连的边设为1
for _ in range(m):
    i,j=map(int,input().split())
    table[i-1][j-1],table[j-1][i-1]=1,1
u,v=map(int,input().split())
#输入起点后重点（因为是从0开始，所有要减1）
u,v=u-1,v-1
#计算成功连通的各个路径的每个节点的访问次数
s_path=[0 for _ in range(n)]
def dfs(start,end):
    global s_path
    #start==end说明已经找到路径了
    if start==end:
        for i in range(n):
            #在每次找到连通路径的时候，都会对访问过的点记为True
            if flag[i]==True:
                s_path[i]+=1
        return
    for i in range(n):
        #如果存在边并且没有访问过
        if table[start][i]==1 and not flag[i]:
            #设置为访问过
            flag[i]=True
            #继续遍历
            dfs(i,end)
            #回溯
            flag[i]=False
dfs(u,v)
#如果找到了路径，最后肯定i==end，所以每次end这个节点都会加1，最终结果就是和
#end次数相同的减去end本身
print(s_path.count(s_path[v])-1)