1 条题解
-
0
C++ :
#include <cstdio> /* 无向图并查集统计连通块个数(自环不影响)。N,M<=20000。 */ static int fa[20005]; int find(int x){ while(fa[x] != x){ fa[x] = fa[fa[x]]; x = fa[x]; } return x; } int main(){ int n, m; if(scanf("%d %d", &n, &m) != 2) return 0; for(int i = 1; i <= n; i++) fa[i] = i; int comp = n; for(int i = 0; i < m; i++){ int x, y; if(scanf("%d %d", &x, &y) != 2) break; int a = find(x), b = find(y); if(a != b){ fa[a] = b; comp--; } } printf("%d\n", comp); return 0; }
- 1
信息
- ID
- 2680
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者