任意点~并查集求联通块

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <queue>
 5 #include <cstring>
 6 #include <string>
 7 using namespace std;
 8 const int maxn = 1e4 + 10;
 9 
10 typedef long long LL ;
11 int fa[maxn], x[maxn], y[maxn];
12 
13 void init(int n) {
14     for (int i = 0 ; i <= n ; i++) {
15         fa[i] = i;
16     }
17 }
18 int find(int p) {
19     while(p != fa[p]) p = fa[p];
20     return p;
21 }
22 int find_set(int p)
23 {
24     while(p!=fa[p]) p=fa[p];
25     return p;
26 }
27 
28 void combine(int p, int q) {
29     int np = find_set(p);
30     int nq = find_set(q);
31     if (np != nq) fa[np] = nq;
32 }
33 
34 int main() {
35     int n;
36     //freopen("DATA.txt","r",stdin);
37     while(scanf("%d", &n) != EOF) {
38         init(n);
39         for (int i = 1 ; i <= n ; i++) {
40             scanf("%d%d", &x[i], &y[i]);
41         }
42         for (int i = 1 ; i < n ; i++)
43             for (int j = i + 1 ; j <= n ; j++)
44                 if (x[i] == x[j] || y[i] == y[j] ) combine(i, j);
45         int ans = 0;
46         for (int i = 1 ; i <= n ; i++)
47             if (fa[i] == i) ans++;
48         printf("%d\n", ans - 1);
49     }
50     return 0;
51 }