java dfs解危险系统（附带思路分析）

二，危险系数

题目描述

问题描述
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。

输入

输入数据第一行包含2个整数n(2 < = n < = 1000), m(0 < = m < = 2000),分别代表站点数，通道数；
接下来m行，每行两个整数 u,v (1 < = u, v < = n; u != v)代表一条通道；
最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。

输出

一个整数，如果询问的两点不连通则输出-1.

样例输入

7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

样例输出

2

思路分析

dfs搜图问题

询问通道是否连通，也就是能走到就true，不能走到就false

关键点，也就是起点到终点无论怎么走也必须经过的点，转换一下，

假如起点到终点有t条路径，也就是说必定经过关键点t次（除起点和终点）

也就是说从起点到终点，经过t次的点就是我们要找的点（除起点和终点）

代码实现

package DayT2;
import java.util.Scanner;
public class Main {
    // 记录顶点个数
    public int n;
    // 记录通道连通情况
    public int[][] arr = null;
    // 记录终点
    public int endQ = -1;
    // 记录能否到终点
    public Boolean flag = false;
    // 记录从起点到终点不同路径下每个点经过的次数（不算起点）
    public int[] dot = null;
    // dfs的vic
    public int[] vic = null;
    public static void main(String[] args) {
        Scanner sca = new Scanner(System.in);
        Main main = new Main();
        //接收顶点数和边数
        main.n = sca.nextInt();
        int m = sca.nextInt();
        main.init();
        //由于是无向图，所以构建邻接矩阵
        for (int i = 0; i < m; i++) {
            int start = sca.nextInt();
            int end = sca.nextInt();
            // 站点x和y连通，也就是说能从x到y，也能从y到x
            main.arr[start][end] = main.arr[end][start] = 1;
        }
        //接收起点，终点
        int startQ = sca.nextInt();
        main.endQ = sca.nextInt();
        //dfs
        int result = main.dfs(startQ, 0, new int[main.n + 1]);
        int count = 0;
        //如果两个点不连通，输出-1
        if(main.flag==false) {
            System.out.println(-1);
        }
        //记录有多少个点是去终点的必经之点
        for (int i = 1; i < main.n + 1; i++) {
            if (main.dot[i] == result) {
                count++;
            }
        }
        // 减去终点
        System.out.println(count - 1);
    }
    private void init() {
        // TODO Auto-generated method stub
        arr = new int[n + 1][n + 1];
        dot = new int[n + 1];
        vic = new int[n + 1];
    }
    /**
     * 
     * @param startQ:到达的点
     * @param step:第几个经过点，0代表起点
     * @param temp:从起点到终点经过的点的数组
     * @return
     */
    private int dfs(int startQ, int step, int[] temp) {
        // TODO Auto-generated method stub
        //如果到达的点为终点，说明已经到了终点，有一条路径了
        if (startQ == endQ) {
            //将从起点到终点经过点的次数加一
            for (int i = 0; i < step; i++) {
                dot[temp[i]]++;
            }
            flag = true;
            return 1;
        }
        int result = 0;
        //遍历该点能到的点
        for (int i = 1; i < n + 1; i++) {
            //如果访问过，continue
            if (vic[i] == 1) {
                continue;
            }
            //如果不连通，continue
            if (arr[startQ][i] == 0) {
                continue;
            }
            //记录经过的点
            temp[step] = i;
            //dfs
            vic[i] = 1;
            result += dfs(i, step + 1, temp);
            vic[i] = 0;
        }
        //返回从startQ到终点路径条数
        return result;
    }
}