蓝桥杯历届试题-危险系数 （Java代码）回溯法解题

解题思路:
这个代码是网上看到一个博主的，有way和cnt的作用不是很清楚，希望看懂的同学可以和我交流一下



注意事项:





参考代码:

import java.util.Scanner;
public class 危险系数 {

    private static int[] vist;
    private static int[] way;
    private static int[] cnt;
    private static int ans = 0;
    private static int[][] map;
    private static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();// 边数
        vist = new int[n + 1];
        way = new int[n + 1];
        cnt = new int[n + 1];
        map = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
            map[p1][p2] = 1;
            map[p2][p1] = 1;
        }
        int s = sc.nextInt();
        int t = sc.nextInt();
        dfs(s, t, 0);

        fun(n);
    }

    private static void dfs(int s, int t, int step) {
        // TODO Auto-generated method stub
        vist[s] = 1;
        way[step] = s;
        if (s == t) {
            ans++;
            for (int i = 0; i <= step; i++) {
                cnt[way[i]]++;
            }
        }
        for (int i = 0; i <= n; i++) {
            if (map[s][i] == 1 && vist[i] == 0) {
                vist[i] =1;
                dfs(i, t, step+1);
                vist[i] =0;
            }
        }
    }

    private static void fun(int n) {
        // TODO Auto-generated method stub
        int sum = 0;
        for (int i = 1; i <= n; i++) {

            if (cnt[i] == ans) {
                sum++;
            }
//          System.out.println("cnt的各个值" + cnt[i]);
        }
        System.out.println(sum-2);
    }

}