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
第一次使用并查集，也是学到了很多。刷题必会之一。
