第一种方法是定义每个数的老大是其自身，通过每次输入的两个数，找到它两的老大，比较大小，循环将所有大的那个老大改为小的那个数，最后输出有几个老大是其自身，案例都能过，提交就错，不知错哪了......
点击查看代码
import java.util.Scanner;
public class hdu1213 {
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
int nn = sc.nextInt();
int[] lda = new int[num]; //定义老大
for (int j = 0; j < num; j++) {
lda[j] = j+1;
}
for (int j = 0; j < nn; j++) {
int a = sc.nextInt();
int b = sc.nextInt();
lda = shu(a, b, lda);
}
int res = 0;
for (int j = 0; j < num; j++) {
if (lda[j]==j+1) {
res++;
}
}
System.out.println(res);
/*if (i != n-1) {
System.out.println();
}*/
}
sc.close();
}
public static int[] shu(int a,int b,int[] ld) {
if(ld[a-1]>ld[b-1]) {
int tmp = a;
a = b;
b = tmp;
}
for (int i = 0; i < ld.length; i++) { //每个数的老大是小于它的一个数
if (ld[i]==ld[b-1]) {
ld[i] = ld[a-1];
}
}
return ld;
}
}
第二种方法是通过找根节点的方式，定义每个老大的根节点是-1，当输入的两个数的老大是不同的时候，将其中一个老大更改。
点击查看代码
import java.util.Scanner;
public class hud1213_1 {
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while(n-- > 0) {
int num = sc.nextInt();
int nn = sc.nextInt();
int[] lda = new int[num];
for (int i = 0; i < lda.length; i++) {
lda[i] = -1;
}
for (int i = 0; i < nn; i++) {
int a = sc.nextInt()-1;
int b = sc.nextInt()-1;
lda = merg(a, b, lda);
}
int res = 0;
for (int i = 0; i < lda.length; i++) {
if (lda[i]==-1) {
res++;
}
}
System.out.println(res);
}
sc.close();
}
//寻找根节点
static int father(int x,int[] lda) {
int index = x;
while (lda[index]!=-1) {
index = lda[index];
}
return index;
}
static int[] merg(int a,int b,int[] lda) {
int x = father(a, lda);
int y = father(b, lda);
//如果两个数的根节点不一样 则改变其中一个数的根节点
if (x!=y) {
lda[x] = y;
}
return lda;
}
}