思路就是簡單並查集
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);
}
}
}