JAVA题解 1433: 蓝桥杯2013年第四届真题-危险系数

解题思路: DFS暴力搜索，使用了全局栈和全局数据存储数据

注意事项:

参考代码:

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

// https://www.dotcpp.com/oj/problem1433.html
// 看似是BFS, 其实需要用dfs搜出所有的路径
public class Main {
    static StreamTokenizer cin;
    static PrintWriter out;
    static int n;  // 站点数
    static int m;  // 通道数
    // 危险系数询问站点
    static int u;
    static int v;
    static boolean[] visited;
    static ArrayList<Integer>[] map;  // 临接表
    static Stack<Integer> stack;
    static long[] count;  // 每个节点的访问次数, 用于寻找关键点
    // 关键点必须在找到的每条路径中都出现
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        n = nextInt();
        m = nextInt();
        map = new ArrayList[n+1];
        visited = new boolean[n+1];  // 访问数组, 防止成环
        count = new long[n+1];
        for(int i = 1; i < n+1; i++)
            map[i] = new ArrayList<>();
        for(int j = 0; j < m; j++){
            int f = nextInt();
            int t = nextInt();
            map[f].add(t);
            map[t].add(f);
        }
        u = nextInt();
        v = nextInt();
        visited[u] = true;
        stack = new Stack<>();
        long paths = dfs(u, v);
        int s = 0;
        if (Arrays.stream(count).sum() == 0)
            out.println(-1);
        else{
            for(int i = 1; i < n+1; i++){
                if(i != v && paths==count[i])
                    s++;
            }
            out.println(s);
        }
        out.flush();
    }
    static long dfs(int u, int v){
        if(u == v){
            for(int index : stack){
                count[index]++;
            }
            return 1;
        }
        int sum = 0;
        for(int node : map[u]){
            if(!visited[node]){  // 该顶点未被访问过
                visited[node] = true;
                stack.push(node);
                sum += dfs(node, v);
                stack.pop();
                visited[node] = false;
            }
        }
        return sum;
    }
    static int nextInt() throws IOException{
        cin.nextToken();
        return (int)cin.nval;
    }
}