蓝桥杯2013年第四届真题-危险系数-题解（Java代码）邻接表+深度优先搜索+桶思想

解题思路:

    所谓关键点既是所有可行的路径都要经过该点，因此，采用深度搜索的方式找到每条路径，并记录路径上的点的访问次数，若二者相同，则为关键点。本人先将通道转化成邻接表，再用DFS寻找路径，同时利用桶思想记录节点访问的次数。

注意事项:

参考代码:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class 关键点 {
    private static HashSet<Integer>[] sets; // 邻接表
    private static ArrayList<Integer> parents = new ArrayList<>();  // 记录之前已遍历过的结点
    private static ArrayList<Integer> routes = new ArrayList<>();   // 记录路径上的结点，不记录头尾
    private static int[] index; //  节点桶，记录路径上的点访问的次数
    private static int count = 0;   //  记录路径的个数
    private static int start;
    private static int end;
    public static void main(String[] args){
        int num = 0;    // 记录关键节点的个数
        Scanner reader = new Scanner(System.in);
        int station_num = reader.nextInt(); // 站点数
        int route_num = reader.nextInt();   // 通道数
        sets = new HashSet[station_num+1];
        index = new int[station_num+1];
        for(int i=1;i<=station_num;i++){
            sets[i] = new HashSet<>();
        }
        for(int i=0;i<route_num;i++){   //建立邻接表
            int former = reader.nextInt();
            int later = reader.nextInt();
            sets[former].add(later);
            sets[later].add(former);
        }
        start = reader.nextInt();   // 起始站点
        end = reader.nextInt(); // 终点
        if(sets[start].isEmpty()||sets[end].isEmpty()){ //  如果起始站点或终点没有其他点相连，则输出-1
            System.out.println(-1);
        }else{
            DFS(start); // 深度搜索，寻找路径
            if(count == 0) {    // 若未找到路径，则输出-1
                System.out.println(-1);

            }else {
                for(int i=1;i<=station_num;i++){    // 若路径上的点的访问次数与路径数相同，则该点是关键点
                    if (index[i] == count)
                        num ++;
                }
                System.out.println(num);
            }

        }

    }

    private static void DFS(int start) {
        Iterator<Integer> iterator = sets[start].iterator();
        parents.add(start);
        while (iterator.hasNext()){ //遍历邻接节点
            int next = iterator.next();
            if(parents.contains(next))continue; //如果已访问过则不再访问
            if(next == end){    // 找到目标则记录起来每个节点访问的次数及路径数
                for(int e : routes)
                    index[e] ++;
                count ++;
            }
            routes.add(next);
            DFS(next);
            parents.remove(parents.size()-1);   // 向上弹出一层，则将该点释放掉，因为还可能从其他路径访问
            routes.remove(routes.size()-1); //  向上弹出，说明该点要么不是路径上的点，要么是已访问过路径上的点，不再记录
        }
        return;
    }
}