一道算法题,算法好或者搞ACM的童鞋看过来~题目在这里：首先说这道题目不是很难,但是我自己想了一个算法,我认为挺对的,使用的例子都能得到正确答案,但是怎么都通不过去,我知道标准的话

一道算法题,算法好或者搞ACM的童鞋看过来~题目在这里：首先说这道题目不是很难,但是我自己想了一个算法,我认为挺对的,使用的例子都能得到正确答案,但是怎么都通不过去,我知道标准的话
一道算法题,算法好或者搞ACM的童鞋看过来~
题目在这里：
首先说这道题目不是很难,但是我自己想了一个算法,我认为挺对的,使用的例子都能得到正确答案,但是怎么都通不过去,
我知道标准的话是用深度优先搜索,但是希望知道这个算法的问题.
我的思想是这样的,缺少的路的条数是联通分支数-1,count代表联通分支数目
import java.util.*;
public class Main {
\x05private class Key{//每个联通子图所有城市的key相等.
\x05\x05int key;
\x05\x05public Key(int k){
\x05\x05\x05this.key = k;
\x05\x05}
\x05\x05public boolean equals(Key key){
\x05\x05\x05return this.key == key.key;
\x05\x05}
\x05}
\x05private class City{//每个城市都有一个标志
\x05\x05Key mark = null;
\x05}
\x05public void caculate(){
\x05\x05Scanner scan = new Scanner(System.in);
\x05\x05
\x05\x05
\x05\x05while(true){
\x05\x05\x05int m=0,n=0;
\x05\x05\x05int x=0,y=0;
\x05\x05\x05int key = 0;
\x05\x05\x05
\x05\x05\x05n = scan.nextInt();//城市的个数
\x05\x05\x05if(n == 0)return;
\x05\x05\x05m = scan.nextInt();//路的个数
\x05\x05\x05int count = n;//count代表的是联通子图的个数,初始为n个.
\x05\x05\x05Key unreach = new Key(-1);
\x05\x05\x05Key keys[] = new Key[m];//一般只用很少几个.
\x05\x05\x05for(int i = 0; i < m; i++){
\x05\x05\x05\x05keys[i] = new Key(-1);
\x05\x05\x05}
\x05\x05\x05City citys[] = new City[n];
\x05\x05\x05for(int i = 0; i < n; i++){
\x05\x05\x05\x05citys[i] = new City();
\x05\x05\x05\x05citys[i].mark = unreach;//孤立点的mark是-1,一开始都是孤立点.
\x05\x05\x05}
\x05\x05\x05for(int j = 0; j < m; j++){
\x05\x05\x05\x05x = scan.nextInt()-1;
\x05\x05\x05\x05y = scan.nextInt()-1;
\x05\x05\x05\x05//if(x!=y){//这种情况考虑错误的输入,自己到自己会出错,但oj一般没有错误输入,故可去掉.
\x05\x05\x05\x05//如果新输入的两个都是孤立点,则分配一个相同的key
\x05\x05\x05\x05if(citys[x].mark.equals(unreach)&&citys[y].mark.equals(unreach)){
\x05\x05\x05\x05\x05keys[key] = new Key(key);
\x05\x05\x05\x05\x05citys[x].mark = keys[key];
\x05\x05\x05\x05\x05citys[y].mark = keys[key];key++;
\x05\x05\x05\x05\x05count--;
\x05\x05\x05\x05}//以下两个,如果有一个是孤立点,则给孤立点分配另一个的key,使他们的特征相同.
\x05\x05\x05\x05else if(!citys[x].mark.equals(unreach)&&citys[y].mark.equals(unreach)){
\x05\x05\x05\x05\x05citys[y].mark = citys[x].mark;
\x05\x05\x05\x05\x05count--;
\x05\x05\x05\x05}else if(citys[x].mark.equals(unreach)&&!citys[y].mark.equals(unreach)){
\x05\x05\x05\x05\x05citys[x].mark = citys[y].mark;
\x05\x05\x05\x05\x05count--;
\x05\x05\x05\x05}//如果都不是孤立点,则把所有分配的key中x的key全都改成y的,两个联通分支的特征相同.
\x05\x05\x05\x05else if(!citys[x].mark.equals(citys[y].mark)){
\x05\x05\x05\x05\x05for(int i = 0; i < key; i++){
\x05\x05\x05\x05\x05\x05if(keys[i].equals(citys[x].mark)){
\x05\x05\x05\x05\x05\x05\x05keys[i].key=citys[y].mark.key;
\x05\x05\x05\x05\x05\x05}
\x05\x05\x05\x05\x05}
\x05\x05\x05\x05\x05count--;
\x05\x05\x05\x05}
\x05\x05\x05\x05//}
\x05\x05\x05}
\x05\x05\x05
\x05\x05\x05System.out.println(count-1);
\x05\x05}
\x05\x05
\x05\x05
\x05}
\x05public static void main(String[] agrs){
\x05\x05Main main = new Main();
\x05\x05main.caculate();
\x05}
}

一道算法题,算法好或者搞ACM的童鞋看过来~题目在这里：首先说这道题目不是很难,但是我自己想了一个算法,我认为挺对的,使用的例子都能得到正确答案,但是怎么都通不过去,我知道标准的话
你好,我已经ac了,下面是ac代码
思路就是简单并查集
41549wujianan20071012Accepted32148 kb1060 msJava/Edit2012-02-01 00:05:46
import java.math.*;
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
public static int father[] = new int[1005];
public static int getFather(int x) {
int ret = x;
while (ret != father[ret]) {
father[ret] = father[father[ret]];
ret = father[ret];
}
return ret;
}
public static void union(int a, int b) {
father[getFather(b)] = father[getFather(a)];
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n, m;
while (true) {
n = cin.nextInt();
if (n == 0) {
break;
}
for (int i = 1; i 0) {
int a, b;
a = cin.nextInt();
b = cin.nextInt();
union(a, b);
m--;
}
boolean t[] = new boolean[1005];
int cnt = 0;
for (int i = 1; i