//这题是我接触并查集的第二题,好顺利AC了! //题目给出几个数据对,在同一个数据对中的人的信仰是相同的,需要你求出在给定的人数中,有几种信仰! //将有相同信仰的人组成一颗树,然后统计数的棵树,再加上还有统计的人数,就可以得出了答案! #include "iostream" #include "memory.h" #include "set" using namespace std; const int maxsize = 50010; set<int> s; int pa[maxsize];//集合每一个元素的父节点是自己本身! int ranks[maxsize];//集合每一个元素的秩 bool visited[maxsize];//集合中的元素是否已经访问! //下面是并查集的三大步骤:先初始化,路径压缩+递归的查找,根据秩的合并! void make_set(int x) { pa[x] = x; ranks[x] = 0; } int find_set(int x) { if (x != pa[x]) pa[x] = find_set(pa[x]); return pa[x]; } void union_set(int x, int y) { x = find_set(x); y = find_set(y); if (x == y) return; if (ranks[x] > ranks[y]) pa[y] = x; else { pa[x] = y; if (ranks[x] == ranks[y]) ranks[y]++; } } int main() { int n, m, i, x, y, count = 0, ans; while (cin >> n >> m) { if (n == 0 && m == 0) break; memset(visited, false, sizeof(visited)); ans = 0; s.clear(); count++; for (i = 1; i <= n; i++) make_set(i); for (i = 1; i <= m; i++) { cin >> x >> y; if (!visited[x]) visited[x] = true; if (!visited[y]) visited[y] = true; union_set(x, y); } for (i = 1; i <= n; i++) { if (!visited[i]) ans++;//没有访问过的元素作为一种信仰! if (visited[i]) s.insert(find_set(i));//统计树的个数! } ans += s.size(); cout << "Case " << count << ": " << ans << endl; } }