Question

一道算法题，算法好或者搞ACM的童鞋看过来~

题目在这里：
http://ac.jobdu.com/problem.php?id=1012
首先说这道题目不是很难，但是我自己想了一个算法，我认为挺对的，使用的例子都能得到正确答案，但是怎么都通不过去，希望路过的大神帮忙解惑~
我知道标准的话是用深度优先搜索，但是希望知道这个算法的问题。

我的思想是这样的，缺少的路的条数是联通分支数-1，count代表联通分支数目
import java.util.*;
public class Main {
private class Key{//每个联通子图所有城市的key相等。
int key;
public Key(int k){
this.key = k;
}
public boolean equals(Key key){
return this.key == key.key;
}
}
private class City{//每个城市都有一个标志
Key mark = null;
}
public void caculate(){
Scanner scan = new Scanner(System.in);

while(true){
int m=0,n=0;
int x=0,y=0;
int key = 0;

n = scan.nextInt();//城市的个数
if(n == 0)return;
m = scan.nextInt();//路的个数
int count = n;//count代表的是联通子图的个数，初始为n个。
Key unreach = new Key(-1);
Key keys[] = new Key[m];//一般只用很少几个。
for(int i = 0; i < m; i++){
keys[i] = new Key(-1);
}
City citys[] = new City[n];
for(int i = 0; i < n; i++){
citys[i] = new City();
citys[i].mark = unreach;//孤立点的mark是-1，一开始都是孤立点。
}
for(int j = 0; j < m; j++){
x = scan.nextInt()-1;
y = scan.nextInt()-1;
//if(x!=y){//这种情况考虑错误的输入，自己到自己会出错，但oj一般没有错误输入，故可去掉。
//如果新输入的两个都是孤立点，则分配一个相同的key
if(citys[x].mark.equals(unreach)&&citys[y].mark.equals(unreach)){
keys[key] = new Key(key);
citys[x].mark = keys[key];
citys[y].mark = keys[key];key++;
count--;
}//以下两个，如果有一个是孤立点，则给孤立点分配另一个的key，使他们的特征相同。
else if(!citys[x].mark.equals(unreach)&&citys[y].mark.equals(unreach)){
citys[y].mark = citys[x].mark;
count--;
}else if(citys[x].mark.equals(unreach)&&!citys[y].mark.equals(unreach)){
citys[x].mark = citys[y].mark;
count--;
}//如果都不是孤立点，则把所有分配的key中x的key全都改成y的，两个联通分支的特征相同。
else if(!citys[x].mark.equals(citys[y].mark)){
for(int i = 0; i < key; i++){
if(keys[i].equals(citys[x].mark)){
keys[i].key=citys[y].mark.key;
}
}
count--;
}
//}
}

System.out.println(count-1);
}

}
public static void main(String[] agrs){
Main main = new Main();
main.caculate();
}

}

Answer 1

你好，我已经ac了，下面是ac代码
思路就是简单并查集
41549 wujianan2007 1012 Accepted 32148 kb 1060 ms Java/Edit 2012-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 <= n; i++) {
father[i] = i;
}
m = cin.nextInt();
while (m > 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 <= n; i++) {
t[i] = false;
}
for (int i = 1; i <= n; i++) {
t[getFather(i)] = true;
}
for (int i = 1; i <= n; i++) {
if (t[i] == true) {
cnt++;
}
}
System.out.printf("%d\n", cnt - 1);
}
}
}

Answer 2

这题给我的感觉是直接找出联通块,然后把联通块看成一个点,在这个新的图中找最小生成树