1、
题意：有n台电脑，距离d以内的两台电脑维修后可以互相联系。一台电脑可以通过一对能够互相联系的电脑中的一个与另一个联系。给出每台电脑的坐标，再给出指令，维修一台电脑或是查询某两台电脑是否能够相互联系。对于每个查询指令输出答案。
思路：很普通的并查集。
代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 using namespace std;
5 const int N = 1010;
6 struct node{
7 double x, y;
8 }c[N];
9 int n, d, f[N], g[N];
10 bool vis[N];
11
12 int find(int x);
13 void merge(int x, int y);
14 bool check(node a, node b);
15 void init();
16
17 int main()
18 {
19 scanf("%d%d", &n, &d);
20 init();
21 for (int i=1;i<=n;i++)
22 {
23 scanf("%lf%lf", &c[i].x, &c[i].y);
24 }
25 char op;
26 int num, cnt = 0, x, y;
27 while (~scanf("%c", &op))
28 {
29 if (op == ‘O‘)
30 {
31 scanf("%d", &num);
32 if (vis[num] == false)
33 {
34 for (int i=1;i<=cnt;i++)
35 {
36 if (check(c[g[i]], c[num]))
37 merge(g[i], num);
38 }
39 cnt++;
40 g[cnt] = num;
41 vis[num] = true;
42 }
43 }
44 else if (op == ‘S‘)
45 {
46 scanf("%d %d", &x, &y);
47 if (find(x) == find(y))
48 puts("SUCCESS");
49 else
50 puts("FAIL");
51 }
52 }
53 return 0;
54 }
55
56 int find(int x)
57 {
58 return f[x] == x ? x : f[x] = find(f[x]);
59 }
60 void merge(int x, int y)
61 {
62 int fx = find(x);
63 int fy = find(y);
64 if (fx != fy)
65 {
66 f[fx] = fy;
67 }
68 }
69 bool check(node a, node b)
70 {
71 double dis = sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
72 return dis <= d;
73 }
74 void init()
75 {
76 for (int i=1;i<=n;i++)
77 f[i] = i;
78 }
2、
题意：学校里有n个学生，m个小组。小组中有一个人疑似得了冠状，那么全小组的人都可能得了。给出每个小组的成员，学生0疑似得了冠状，那么求有多少个人被怀疑。
思路：比第一题更普通的并查集。
代码：
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 using namespace std;
5 const int N = 3e4+5;
6 int f[N], n, m;
7
8 int find(int x);
9 void merge(int x, int y);
10 void init();
11
12 int main()
13 {
14 while (scanf("%d %d", &n, &m) && (n || m))
15 {
16 init();
17 for (int i=1;i<=m;i++)
18 {
19 int k, y;
20 scanf("%d", &k);
21 scanf("%d", &y);
22 for (int j=2;j<=k;j++)
23 {
24 int x;
25 scanf("%d", &x);
26 merge(y, x);
27 }
28 }
29 int cnt = 0;
30 for (int i=0;i<n;i++)
31 {
32 if (find(i) == 0)
33 cnt++;
34 }
35 if (m == 0) cnt = 1;
36 printf("%d\n", cnt);
37 }
38 return 0;
39 }
40
41 int find(int x)
42 {
43 return f[x] == x ? x : f[x] = find(f[x]);
44 }
45 void merge(int x, int y)
46 {
47 int fx = find(x);
48 int fy = find(y);
49 if (fx != fy)
50 f[max(fx, fy)] = min(fx, fy);
51
52 }
53 void init()
54 {
55 for (int i=0;i<n;i++)
56 f[i] = i;
57 }
3、
1 #include <cstdio>
2 #include <cstring>
3 using namespace std;
4 const int N = 1010;
5 int T, n, m, f[N];
6 bool vis[N];
7
8 int find(int x);
9 void merge(int x, int y);
10 void init();
11
12 int main()
13 {
14 scanf("%d", &T);
15 while (T--)
16 {
17 memset(vis, 0, sizeof(vis));
18 scanf("%d %d", &n, &m);
19 init();
20 for (int i=1;i<=m;i++)
21 {
22 int x, y;
23 scanf("%d %d", &x, &y);
24 merge(x, y);
25 }
26 int cnt = 0;
27 for (int i=1;i<=n;i++)
28 {
29 int k = find(i);
30 if (vis[k] == false)
31 {
32 vis[k] = true;
33 cnt++;
34 }
35 }
36 printf("%d\n", cnt);
37 }
38 return 0;
39 }
40
41 int find(int x)
42 {
43 return f[x] == x ? x : f[x] = find(f[x]);
44 }
45 void merge(int x, int y)
46 {
47 int fx = find(x);
48 int fy = find(y);
49 if (fx != fy)
50 f[fx] = fy;
51 }
52 void init()
53 {
54 for (int i=1;i<=n;i++)
55 f[i] = i;
56 }
哟，这不并查集吗？几天不见，这么拉了？
4、
[kuangbin带我飞]专题五--并查集 （2/14）How Many Tables HDU - 1213
原文：https://www.cnblogs.com/FantaDevourer/p/12740754.html