Introduction
当今世界上有许多不同的明星，你想知道你们学校的学生总共喜欢多少个不同的明星。
你知道你的大学里有n个学生(0 < n ≤ 50000)，你问每个学生他们喜欢的明星是不可能的。此外，许多学生不好意思说出他们喜欢哪个明星。避免这些问题的一种方法是问m (0≤ m ≤ n(n-1)/2)对学生，问他们是否喜欢相同的明星(例如，他们可能知道他们是否观看同一场演出)。从这些数据中，你可能不知道每个人具体喜欢哪个明星，但你可以知道校园里最多有多少个不同的被喜欢的明星。你可以假设每个学生最喜欢的只有一个明星。
Input
输入由多组用例组成。每一种情况都以整数n和m作为的一行开始，接下来的m行分别由两个整数i和j组成，表示学生i和j喜欢相同的明星。学生被编号为1到n。输入的结束由一行指定，其中n = m = 0。
Output
对于每个测试用例，在单行上打印案例号(以1开头)，后面跟着该大学学生所喜欢的不同明星的最大数量。
Sample
input
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
output
Case 1: 1
Case 2: 7
Solution
package week3;
import java.util.Scanner;
class UnionFind{
private int[] id;
private int[] sz;
public int count;
public UnionFind(int count){
this.count=count;
id=new int[count];
sz=new int[count];
for(int i=0;i<count;i++){
id[i]=i;
sz[i]=1;
}
}
public int find(int x){
if(id[x]!=x){
id[x]=find(id[x]);
}
return id[x];
}
public void union(int x,int y){
int xRoot=find(x);
int yRoot=find(y);
if(xRoot!=yRoot){
if(sz[xRoot]>sz[yRoot]){
id[yRoot]=xRoot;
sz[xRoot]+=sz[yRoot];
}else {
id[xRoot]=id[yRoot];
sz[yRoot]+=sz[xRoot];
}
count--;
}
}
}
public class Main {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int index=1;
while(true){
int n=s.nextInt();int m=s.nextInt();
if(n==0&m==0){
break;
}
UnionFind unionFind=new UnionFind(n);
while (m--!=0){
int x=s.nextInt();int y=s.nextInt();
unionFind.union(x-1,y-1);
}
System.out.println("Case "+index+": "+unionFind.count);
index++;
}
}
}
Experience
第一次使用并查集，也是学到了很多。刷题必会之一。
