54 lines
1.3 KiB
C++
54 lines
1.3 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
class Dsu {
|
|
public:
|
|
struct Node {
|
|
size_t parent, size;
|
|
};
|
|
|
|
vector<Node> nodes;
|
|
|
|
explicit Dsu(const size_t size) : nodes(size) {
|
|
for (size_t i = 0; i < size; i++) {
|
|
nodes[i] = {.parent = i, .size = 0};
|
|
}
|
|
}
|
|
|
|
size_t find(const size_t x) {
|
|
if (nodes[x].parent == x) { return x; }
|
|
return nodes[x].parent = find(nodes[x].parent);
|
|
}
|
|
|
|
void unite(size_t x, size_t y) {
|
|
if ((x = find(x)) == (y = find(y))) { return; }
|
|
if (nodes[x].size > nodes[y].size) { swap(x, y); }
|
|
nodes[x].parent = y;
|
|
nodes[y].size += nodes[x].size;
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
size_t students_count, pairs_count;
|
|
for (int case_id = 1; cin >> students_count >> pairs_count && students_count; case_id++) {
|
|
cout << "Case " << case_id << ": ";
|
|
Dsu dsu(students_count);
|
|
size_t x, y, ans = 0;
|
|
for (int _ = 0; _ < pairs_count; _++) {
|
|
cin >> x >> y;
|
|
dsu.unite(x - 1, y - 1);
|
|
}
|
|
for (size_t node_id = 0; node_id < students_count; node_id++) {
|
|
ans += node_id == dsu.find(node_id);
|
|
}
|
|
cout << ans << endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|