蓝桥杯 危险系数 JAVA

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 import java.util.Scanner;
 4 import java.util.concurrent.ArrayBlockingQueue;
 5 
 6 public class 危险系数 {
 7     static int count = 0; //路径总数
 8     static boolean[] visited = null; //是否为访问过
 9     static int[] way = null; //记录路径  way[k]表示第k步经过的结点
10     static int[] cnt = null; //用于统计该点已经走过几次  cnt[k]表示第k个节点被走过的次数
11     public static void main(String[] args) {
12         Scanner sc = new Scanner(System.in);
13         int station = sc.nextInt();
14         int channel = sc.nextInt();
15         sc.nextLine();
16         
17         visited = new boolean[station];
18         way = new int[station];
19         cnt = new int[station];
20         
21         List<Integer>[] channels = new ArrayList[station];
22         for(int i=0;i<station;i++){
23             channels[i] = new ArrayList<>();
24         }
25         
26         for(int i=0;i<channel;i++){
27             int x = sc.nextInt() -1;
28             int y = sc.nextInt() -1;
29             sc.nextLine();
30             channels[x].add(new Integer(y));
31             channels[y].add(new Integer(x));
32         }
33         
34         int start = sc.nextInt() -1;
35         int end = sc.nextInt() -1;
36         DFS(channels,start,end,0);
37         System.out.println(GetResult());
38     }
39     
40     public static void DFS(List<Integer>[] channels,int start,int end,int k){
41         visited[start] = true;
42         way[k] = start;
43         if(start==end){
44             count++;
45             for(int i=0;i<k;i++){
46                 cnt[way[i]]++; //将路径经过的每个节点的次数加1
47             }
48             return ;
49         }
50         
51         for(int i=0;i<channels[start].size();i++){
52             int temp = channels[start].get(i); 
53             if(!visited[temp]){
54                 DFS(channels, temp, end, k+1);
55                 visited[temp] = false;
56             }
57             
58         }
59 
60     }
61     
62     public static int GetResult(){
63         int sum = 0;
64         for(int i=0;i<cnt.length;i++){
65             if(cnt[i]==count){ //如果该节点的经过次数等于路径的数目，则表明该节点是必经节点
66                 sum++;
67             }
68         }
69         return sum - 1;
70     }
71 }