python-危险系数

解题思路:

深度搜索DFS。

DFS的算法就不再过多解释了，说一下如何判断关键点的个数。

利用DFS找到所用能从u到v的路径。记录下来每个站点在路径中每出现一次就进行+1。

我们可以知道v站点的访问次数就等于路径数。在除了v站点的所有站点中，凡是访问次数等于v站点的访问次数的站点都是关键点。找出这些站点，输出这些站点的个数即可。

注意事项:

参考代码:

def dfs(now,end):  
    global Path,Visit,Node_times  
  
    if now == end:  
        for i in range(1,n+1):  
            if Visit[i]:  
                Node_times[i] = Node_times[i]+1  
        return  
  
    for i in range(1,n+1):  
        if Path[now][i] and (not Visit[i]):  
            Visit[i] = 1  
            dfs(i,end)  
            Visit[i] = 0  
              
      
  
if __name__ == '__main__':  
    n,m = map(int,input().strip().split())  
    Path = [[0 for j in range(n+1)] for i in range(n+1)]  
    Visit = [0 for i in range(n+1)]  
    Node_times = [0 for i in range(n+1)]  
  
    for i in range(m):  
        a,b = map(int,input().strip().split())  
        Path[a][b] = 1  
        Path[b][a] = 1  
          
    start,end = map(int,input().strip().split())  
    dfs(start,end)  
    print(Node_times.count(Node_times[end])-1)