-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathP1536.c
More file actions
44 lines (40 loc) · 763 Bytes
/
P1536.c
File metadata and controls
44 lines (40 loc) · 763 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 1001
int p[N];
int find(int a) {
if (p[a] < 0) return a;
return p[a] = find(p[a]);
}
int merge(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb)
return 0;
if (p[ra] < p[rb]) {
p[ra] += p[rb];
p[rb] = ra;
}
else {
p[rb] += p[ra];
p[ra] = rb;
}
return 1;
}
int main() {
int n, m, i, a, b;
scanf("%d", &n);
while (n) {
memset(p, -1, n*4);
scanf("%d", &m);
for (i = 0; i < m; i++) {
scanf("%d %d", &a, &b);
a--; b--;
if (merge(a, b)) n--;
}
printf("%d\n", n - 1);
scanf("%d", &n);
}
exit(0);
}