经典并查集
#include <iostream> using namespace std; int m,n,case_t,parent[50050]; int num[50050]; void makeset() { int x; for(x=1;x<=n;x++) { parent[x]=x; num[x]=0; } } int findset(int x) { if(parent[x]!=x) parent[x]=findset(parent[x]); return parent[x]; } void unionset(int x,int y) { x=findset(x); y=findset(y); if(parent[x]==parent[y]) return ; parent[y]=x; } int main() { int i,j,x,y; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0) break; case_t++; makeset(); for(i=0;i<m;i++) { scanf("%d%d",&x,&y); unionset(x,y); } int sum=0; for(i=1;i<=n;i++) if(i==parent[i]) sum++; printf("Case %d: %d/n",case_t,sum); } return 0; }
