某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
对每个测试用例,在1行里输出最少还需要建设的道路数目。
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
output
1
0
2
998
Huge input, scanf is recommended.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| import java.io.*; import java.util.*; public class Main{ public static int pre[]; public static int m,n; public static Edge []edges; static class Edge implements Comparable<Edge>{ public int u,v,w; public int compareTo(Edge e){ return this.w-e.w; }
} public static int find(int x){ int r = x; while(pre[r]!=r) r=pre[r]; int j=x,tmp; while(j!=r) { tmp = pre[j]; pre[j] = r; j = tmp; } return r; } public static int kruskal(){ int tot=1,sum=0; for(int i=1;i<=m&&tot<=n;i++) {
int a = find(edges[i].u); int b = find(edges[i].v); if(a!=b){ sum+=edges[i].w; pre[a] = b; tot++; } } return sum; } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer;
public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; }
public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); }
public int nextInt() { return Integer.parseInt(next()); }
} public static void main(String []args) { InputReader sc = new InputReader(System.in); while(true){ n = sc.nextInt(); m = n*(n-1)/2;
if(n==0) break; pre = new int[n+1]; for(int i=1;i<=n;i++) pre[i] = i;
edges = new Edge[m+1]; for(int i=1;i<=m;i++) edges[i] = new Edge(); int c; for(int i=1;i<=m;i++) { edges[i].u = sc.nextInt(); edges[i].v = sc.nextInt(); edges[i].w = sc.nextInt(); c = sc.nextInt(); if(c==1) edges[i].w = 0; } Arrays.sort(edges,1,edges.length); System.out.println(kruskal()); } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| import java.util.Scanner; public class Demo1 { static class Union{ private int parent[]; private int count; public Union(int count){ parent = new int[count+1]; this.count = count; for (int i = 1; i <= count; i++) { parent[i] = i; } } int find(int p){ return p == parent[p] ? p : find(parent[p]); } void unionElements(int p,int q){ int pRoot = find(p); int qRoot = find(q); if (pRoot==qRoot){ return; } parent[pRoot] = qRoot; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int count = 0; while (sc.hasNext()){ count = 0; int n = sc.nextInt(); if (n==0) break; int m = sc.nextInt(); Union union = new Union(n); for (int i = 0; i < m; i++) { int x = sc.nextInt(); int y = sc.nextInt(); union.unionElements(x,y); } for (int i = 1; i <= n; i++) { if (union.parent[i]==i){ count++; } } System.out.println(count-1); } } }
|
参考文章