文章目录
前言
一、例题，代码
1.AcWing 836. 合并集合
本题分析
AC代码
2.AcWing 837. 连通块中点的数量
关于本题
AC代码
3.AcWing 240. 食物链
关于本题
AC代码
二、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：并查集，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、例题，代码
1.AcWing 836. 合并集合
本题链接：合并集合
本博客给出本题的截图：
本题分析
如何合并两个集合：让它们的父节点相等
刚开始对于每一个点都是一个单独的集合
数组p代表着父节点，例如p[i]的值就是i的父节点的值
p数组的初始化p[i] = i;，如何合并两个集合呢？例如合并3和5这两个数所在的集合
那么一开始p[3] = 3, p[5] = 5，我们令p[3] = p[5] = 5，这一步的操作是让3的父节点指向5，即让5是3的父节点，我们写成p[5] = p[3] = 3也是可以的，二者没有本质的差别
那么如果我们紧接着想让2和3所在的集合进行合并，我们知道了现在3和5是在一个集合的，并且3的父节点是5，那么我们执行p[2] = p[find(3)]，find(x)函数为查找x的父节点，执行完这个操作我们可以让2的父节点也指向5，从而达到集合合并的目的
find函数：我们查找p[x]和x是否相等，因为我们一开始都是让p[i] = i;，如果不相等，证明该点和别的集合进行了合并，那么我们就去继续寻找该点的父节点即p[x] = find(p[x].
AC代码
#include <cstdio> using namespace std; const int N = 100010; int p[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) p[i] = i; while (m -- ) { char op[2]; scanf("%s", op); int a, b; scanf("%d%d", &a, &b); if (op[0] == 'M') p[find(a)] = find(b); else if (p[find(a)] == find(b)) puts("Yes"); else puts("No"); } return 0; }
2.AcWing 837. 连通块中点的数量
本题链接：AcWing 837. 连通块中点的数量
本博客给出本题截图：
关于本题
相较于上一个题，我们还需要多维护一个cnt数组，因为每一个数一开始都是一个集合，所以每个集合的初始值为1，即cnt[i] = 1;
AC代码
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int N = 100010; int p[N], cnt[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); else return p[x]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) { p[i] = i; cnt[i] = 1; } while (m -- ) { string op; cin >> op; if (op == "C") { int a, b; scanf("%d%d", &a, &b); if (find(a) != find(b)) { cnt[find(b)] += cnt[find(a)]; p[find(a)] = find(b); } } else if (op == "Q1") { int a, b; scanf("%d%d", &a, &b); if (p[find(a)] == p[find(b)]) puts("Yes"); else puts("No"); } else { int x; scanf("%d", &x); printf("%d\n", cnt[find(x)]); } } return 0; }
3.AcWing 240. 食物链
本题链接：AcWing 240. 食物链
本博客给出本题截图：
关于本题
分析过程有点复杂，文字性语言不好说清，未来会放一个文字版解释或一个视频讲解，先鸽
若有视频讲解，链接为（先鸽）
AC代码
#include <cstdio> using namespace std; const int N = 50010; int p[N], d[N]; int find(int x) { if (p[x] != x) { int t = find(p[x]); d[x] += d[p[x]]; p[x] = t; } return p[x]; } int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; i ++ ) p[i] = i; int res = 0; while (k -- ) { int x, y, q; scanf("%d%d%d", &q, &x, &y); int px = find(x), py = find(y); if (x > n || y > n) res ++; else { if (q == 1) { if (px == py && (d[x] - d[y]) % 3) res ++; else if (px != py) { p[px] = py; d[px] = d[y] - d[x]; } } else { if (px == py && (d[x] - d[y] - 1) % 3) res ++; else if (px != py) { p[px] = py; d[px] = d[y] + 1 - d[x]; } } } } printf("%d", res); return 0; }
二、时间复杂度
关于并查集算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
