做滋补品销售有什么网站,深圳营销型网站建设-龙华信科,网站建设语言环境,东莞专业网站建设公司Input 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数#xff0c;分别是城镇数目N ( 1000 )和道路数目M#xff1b;随后的M行对应M条道路#xff0c;每行给出一对正整数#xff0c;分别是该条道路直接连通的两个城镇的编号。为简单起见#xff0c;城镇…Input 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数分别是城镇数目N ( 1000 )和道路数目M随后的M行对应M条道路每行给出一对正整数分别是该条道路直接连通的两个城镇的编号。为简单起见城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时输入结束该用例不被处理。 Output 对每个测试用例在1行里输出最少还需要建设的道路数目。 Sample Input 4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0 Sample Output 1 0 2 998 这题是一个很经典的并查集题目了也是最基础的了当做学习~ import java.util.Scanner;public class Main {public static int[] parent;public static boolean[] root;public static int find(int x){int top x; //找出顶层父节点while(parent[top] ! top){top parent[top];}//减少深度路径压缩int c2 x; int temp;while(c2!top){temp parent[c2];parent[c2] top;c2 temp;}return top;}public static void union(int x,int y){int fx find(x);int fy find(y); //如果不是同一顶层父节点则随机一个联合if(fx ! fy){parent[fy] fx;}}public static void main( String[] args ) {Scanner sc new Scanner(System.in);int n,m;while(sc.hasNext()){int answer0;n sc.nextInt();if(n0) return ;m sc.nextInt();parent new int[n1];root new boolean[n1];for(int i1;in;i){parent[i] i;}for(int i0;im;i){union( sc.nextInt(), sc.nextInt() );}for(int i1;in;i){root[find( i )] true;}for(int i1;in;i){if(root[i]){answer;}}System.out.println( answer-1 );}}
} 转载于:https://www.cnblogs.com/dick159/p/5287760.html
