1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define MAX 50001 6 using namespace std; 7  8 int caseNum,student,pairNum; 9 typedef struct node{10     int data_;//节点对应人的编号11     int rank_;//节点对应的秩12     int parent_;//节点对应双亲下标13 }UFSTree;14 void MAKE_SET(UFSTree t[]);//初始化并查集树15 int FIND_SET(UFSTree t[],int x);//在x所在子树中查找集合编号16 void UNION(UFSTree t[],int x,int y);//将x和y所在的子树合并17 int main()18 {19     //freopen("D:\\acm.txt","r",stdin);20     int cycle = 0;21     while(cin>>student>>pairNum,student&&pairNum){22         int flag = student;23         UFSTree t[MAX];24         MAKE_SET(t);25         for(int m = 0;m < pairNum;m++){26             int x,y;27             cin>>x>>y;28             if(FIND_SET(t,x)!= FIND_SET(t,y)){29                 flag--;30                 UNION(t,x,y);31             }32         }33         cycle++;34         cout<<"Case "<<cycle<<": "<<flag<<endl;35     }36     return 0;37 }38 void MAKE_SET(UFSTree t[]){39     for(int i = 1;i <= student;i++){40         t[i].data_ = i;//数据为该人编号41         t[i].rank_ = 1;//秩，即节点的个数42         t[i].parent_ = i;//父节点指向自己43     }44 }45 int FIND_SET(UFSTree t[],int x){46     if(x != t[x].parent_){47         return (FIND_SET(t,t[x].parent_));48     }49     else50         return x;51 }52 void UNION(UFSTree t[],int x,int y){53     x = FIND_SET(t,x);54     y = FIND_SET(t,y);55     if(x==y)return;56     if(t[x].rank_ > t[y].rank_){57             t[y].parent_ = x;58             t[x].rank_ += t[y].rank_;59     }60     else{61         t[x].parent_ = y;62         t[y].rank_ += t[x].rank_;63     }64 }