[cpp] #include <iostream> #include <cstdio> using namespace std; int f[50010]; int sum = 0; //Accepted 360K 313MS int find1(int x) { if(f[x] != x) { f[x] = find1(f[x]); } return f[x]; } void merge1(int a, int b) { int f1 = find1(a); int f2 = find1(b); if(f1 != f2) { f[f2] = f1; sum--; } } int main() { int n, m, p = 1; while(scanf("%d%d", &n, &m) != EOF) { if( n == 0 && m == 0) { break; } for(int i = 1; i <= n; i++) { f[i] = i; } sum = n; for(int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); merge1(a, b); } printf("Case %d: %d\n", p++, sum); } return 0; } ／／另一版本，大概思路相似，僅僅就並的時候，少的像多的並。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; //Accepted 556K 297MS struct student { int index; int num; student(){ num = 1; } }; student f[50010];///剛剛開始數組開小了，runtime error! int n, m, sum = 0; int find1(int x) {//查找 if(f[x].index != x) { f[x].index = find1(f[x].index); } return f[x].index; } void merge1(int a, int b){ //合並 int f1 = find1(f[a].index); int f2 = find1(f[b].index); if(f1 != f2) { if(f[f1].num >= f[f2].num) { f[f1].num += f[f2].num; f[f2].index = f1; } else { f[f2].num += f[f1].num; f[f1].index = f2; } sum--; } } void init() {//初始化 sum = n; for(int i = 1; i <= n; i++) { f[i].index = i; } } int main() { int p = 1; while(scanf("%d%d", &n, &m) != EOF) { if(!n && !m) { break;} init(); for(int i = 1; i <= m; i++) { int a, b; scanf("%d%d", &a, &b); merge1(a, b); } printf("Case %d: %d\n", p++, sum); } return 0; }
