题目链接。
分析:
给定 n 个点和 m 条无项边,求连通分量的数量。用并查集很简单。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <map> #include <queue> #include <cmath> using namespace std; const int maxn = 50000 + 10; int p[maxn]; int find(int x) { return x == p[x] ? x : (p[x] = find(p[x])); } int main(){ int n, m, a, b, kase = 0; while(scanf("%d%d", &n, &m) == 2) { if(n == 0 && m == 0) break; for(int i=1; i<=n; i++) p[i] = i; int cnt = 0; for(int i=0; i<m; i++) { scanf("%d %d", &a, &b); int x = find(a), y = find(b); if(x != y) { p[x] = y; } } for(int i=1; i<=n; i++) { if(p[i] == i) cnt++; } printf("Case %d: ", ++kase); printf("%d ", cnt); } return 0; }