X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路，构成通信网。 两个空间站间可能直接通信，也可能通过其它空间站中转。 对于两个站点x和y (x != y), 如果能找到一个站点z，使得： 当z被破坏后，x和y无法通信，则称z为关于x,y的关键站点。 显然，对于给定的两个站点，关于它们的关键点的个数越多，通信风险越大。 你的任务是：已知网络结构，求两站点之间的通信风险度，即：它们之间的关键点的个数。 输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，链路数。 空间站的编号从1到n。通信链路用其两端的站点编号表示。 接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。 最后1行，两个数u,v，代表被询问通信风险度的两个站点。 输出：一个整数，如果询问的两点不连通则输出-1. 例如： 用户输入： 7 6 1 3 2 3 3 4 3 5 4 5 5 6 1 6 则程序应该输出： 2 资源约定： 峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 2000ms

用并查集做这道题：这个讲的挺好的：http://www.cnblogs.com/TonyNeal/p/bingchaji.html

思路：用并查集储存输入数据；看是否连通；否直接输出-1；

是则遍历删除每一个点，再用并查集储存删除后的数据，看是否连通；

不能连通，这个点就是关键点；

画了个很蠢的图：

表格里是每次输入数据pre[i]的变化；i代表从1-n的节点；pre[i]代表i这个节点的父节点；

通过join函数连接后，你会发现图右边里的点都被连上了；比如找1和6:操作完后的1的父节点是3,3的父节点是6,6的父节点是6；则1和6是连通的

并查集算法和路径压缩

http://www.cnblogs.com/TonyNeal/p/bingchaji.html

import java.util.Scanner; public class 风险度量2 { static int pre[]; private static int count; public static void main(String[] args) { // TODO Auto-generated method stub Scanner input = new Scanner(System.in); int n = input.nextInt(); int m = input.nextInt(); int init[][] = new int[n][2]; pre = new int[n+1]; for (int i = 1; i < pre.length; i++) { pre[i] = i;//现在从1到n节点的父节点都是自己；设置i为根节点 } //连接两个点 for (int i = 0; i < m; i++) { init[i][0] = input.nextInt(); init[i][1] = input.nextInt(); join(init[i][0],init[i][1]); } //要判断的两个点 int start = input.nextInt(); int end = input.nextInt(); if (find(start)!=find(end)) {//如果不连通直接结束了 System.out.println("-1"); return; } //现在遍历每个点，去掉这个点，剩下的点再重新用并查集找跟节点；若start和end连不上了，说明这个点是关键点 for (int i = 1; i <= n; i++) {//1-n个点 //如何去掉这个点呢？跟程序开头一样，只要init[j]数组里面有i这个点的都不进行join操作； if (i==start||i==end) { continue;//不可能把两个端点去了吧。 } for (int j2 = 1; j2 <= n; j2++) { //既然和程序开头一样，那么pre也要重置才行； pre[j2] = j2;//切记复制的时候变量要改啊。。。 } for (int j = 0; j < m; j++) { if (init[j][0]==i||init[j][1]==i) { continue;//这一步就是去掉i这个点 }else { join(init[j][0], init[j][1]); } } if (find(start)!=find(end)) { count++;//连接不上，这是个关键点 } } System.out.println(count); } /** * @param i i节点 * @param j j节点 */ private static void join(int i, int j) { // TODO Auto-generated method stub i = find(i);//i=i的父节点；取出pre[i]； j = find(j); if (i!=j) {//如果i和j的父节点不一样，让j成为i的父节点； pre[i] = j; } } /** * @param i * @return i的根节点 */ private static int find(int i) { // TODO Auto-generated method stub int x = i; while (x!=pre[x]) {//如果i的父节点不是自己；意思i不是根节点 x = pre[x]; } //路径压缩，让i到根节点上的所有点的父节点都变成根节点； int y = i; int temp = 0; while (y!=x) {//y不等于根节点的时候 temp = pre[y];//临时变量记录y的父节点； pre[y]=x;//y的父节点直接变成根节点； y = temp;//令y等于y的父节点，便于把他父节点的父节点也变成根节点; } return x; } }