蓝桥杯2013年第四届真题-危险系数-题解(Python代码) DFS

m,n=map(int,input().split())
l = [[0 for _ in range(m)] for _ in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    l[a-1][b-1]=1
    l[b-1][a-1]=1
start,end = map(int,input().split())
start,end=start-1,end-1
vis = [False for i in range(m)]
ss_time=0
s_path=[0 for i in range(m)]
def dfs (start,end):
    global ss_time
    global s_path
    if start==end :
        ss_time+=1
        for i in range(m):
            if vis[i]==True:
                s_path[i]+=1
    for i in range(m):
        if l[start][i]==1 and not vis[i]:
            #print(i)
            vis[i]=True
            dfs(i,end)
            vis[i]=False
dfs(start,end)
print(s_path.count(ss_time)-1)