蓝桥杯2013年第四届真题-危险系数 （Java代码）

前提说明：在看了之前的一位前辈写的过后，本人添加了大部分的解释，供大家学习
参考代码:

import java.util.Scanner;

//也就是说，这个回溯算法算的 就是记录有多少条路，以及每个点所经过的次数，如果路数与点的经过的次数相同，则这个点为关键点

public class Main{

private static int[] visit;  //记录点有没有被访问

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();  //得到边的个数

     visit = new int[n+1];  //根据点的个数建立一位数组

     for(int i=0;i<=n;i++) {

         visit[i] = 0;

    }

     way = new int[n+1];

     cnt = new int[n+1];

     for(int i=0;i<=n;i++) {

         cnt[i] = 0;

     }

     map = new int[n+1][n+1];

     for(int i =0;i<n;i++) {

         for(int j=0;j<n;j++) {

             if(i==j)map[i][j] = 0;

                 else map[i][j]=-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);

    }

     public static void dfs(int s,int t,int step) {  //用来找到所有可行的路线，以及线上每个点的经过次数

         visit[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&&visit[i]==0) {   //如果有边而且没有访问过

                 visit[i] = 1;                 // 标记访问到了

                 dfs(i, t, step+1);//在从这个点访问之后的点是否有边

                 visit[i] = 0;

              }

        }

    }

     public static void fun(int n) {

         int sum = 0;

         for(int i=0;i<=n;i++) {

             if(cnt[i]==ans) {

             sum++;

             }

         }

         System.out.println(sum-2);  //减去起始两个点

     }

}