Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 80850 Accepted Submission(s): 42813
Status | Accepted |
---|---|
Time | 31ms |
Memory | 1392kB |
Length | 966 |
#include <bits/stdc++.h> using namespace std; const int maxn = 10001; int N, M; int p[maxn]; int cnt[maxn]; int ans; int ffind(int x) { return p[x] == x? x : p[x] = ffind(p[x]); } void init(int n) { ans = 1; for(int i = 1; i <= n ; i++) p[i] = i, cnt[i] = 1; } void uunion(int u, int v) { int a = ffind(u); int b = ffind(v); if(a != b) p[b] = a, cnt[a] += cnt[b], cnt[b] = 0; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r",stdin); freopen("out.txt", "w",stdout); #endif // ONLINE_JUDGE while(~scanf("%d %d", &N, &M) && N) { init(N); int a,b; for(int i = 0; i < M; i++) { scanf("%d%d", &a, &b); uunion(a,b); } int num = 0; for(int i = 1; i <= N; i++) { // printf("cnt[%d]: %d", i , cnt[i]); if(cnt[i] != 0) num++; } printf("%d\n", num - 1); } return 0; }
原文:https://www.cnblogs.com/YY666/p/11222344.html