HDU 1232 裸的并查集
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <bits/stdc++.h>using namespace std;const int maxn = 1000 + 10;int fa[maxn];int find(int x) { return fa[x] == x ? x: fa[x] = find(fa[x]);}int main() { int n, m, x, y; while(~scanf("%d%d",&n, &m) && n) { for(int i = 1; i <= n; i++) fa[i] = i; int cur = 0; while(m--) { scanf("%d%d",&x, &y); int fx = find(x); int fy = find(y); if(fx != fy) fa[fx] = fy, cur++; //并了cur次 } printf("%d
",n - 1 - cur); }} |