抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数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 思路：从头到尾把每个站点遍历一遍（ 除要查询的站点），当遍历到某个站点时将这个站点的相关路径去掉，并重新建立起并查集，最后判断是否连通，即可知道该站点是否为关键点。关于并查集的相关概念，之前做 poj 2524已经总结，不清楚的可以看一下（POJ 2524 解题报告（并查集））
比如样例:
如果建立起并查集是：
遍历站点：
由于1即为查询的站点，所以从第2个站点开始遍历， 去掉站点2相关路径，再次建立并查集：
虽然去掉了站点2，但是站点1，站点6依然是连通的，故站点2不是关键点
去掉站点3及其相关路径：
这时，我们发现，站点1，站点6不连通，故站点3为关键点。同理去掉站点4，5，7，分别建立相应的并查集，可以发现，站点3，站点5是关键点，删掉其他站点，站点1与站点6之间的连通性不改变，所以样例答案是2
AC代码：
import java.util.Scanner; public class Main { static int team[];// 分组 static int road[][];// 路径 public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int count = 0; int n = in.nextInt(); int m = in.nextInt(); road = new int[m][2]; team = new int[n + 1]; for (int i = 0; i < m; i++) {// 路径存储 road[i][0] = in.nextInt(); road[i][1] = in.nextInt(); } int a = in.nextInt(); int b = in.nextInt();// 读入要查询连通性的两个站点 createSet(0);//没有0站点，故可以建立完整的关系，不会删掉任何一个站点 if (find(a) != find(b)) { count = -1;//如果一开始就没有连通，那么直接输出-1 } else { for (int i = 1; i <= n; i++) { if (i != a && i != b) { createSet(i);// 建立并查集 if (find(a) != find(b))// 判断是否连通 count++; } } } System.out.println(count);// 输出连通数 } in.close(); } private static void createSet(int key) { for (int i = 1; i < team.length; i++) {// 初始化分组，刚开始每个人自己各位一组 team[i] = i; } for (int i = 0; i < road.length; i++) { if (road[i][0] != key && road[i][1] != key) { union(road[i][0], road[i][1]);// 合并 } } } private static boolean union(int a, int b) { int fa = find(a); int fb = find(b); if (fa != fb) { team[fa] = fb; return true; } return false; } private static int find(int k) { if (k == team[k]) return k; return team[k] = find(team[k]); } }