20251206 - 并查集总结
如果要求出两个东西是否在集合里，怎么办？
把它存在图里，再离线处理。
Tarjan 巨佬提出了并查集。
查找
如果要判断两个人是否是同一个省的人，可以问问你们的代表人物是谁？
如果相同，就是同一个省的。
所以，记录每一个元素的父亲，再每次向上找即可。
递归版：
int find(int x) {if (fa[x] == x) return x;return find(fa[x]);
}
迭代版:
int find(x) {while (fa[x] != x) {x = fa[x];}return x;
}
合并
合并时，找到两个集合的代表元，把一个集合的代表元改到另一个即可。
void unite(int x, int y) {x = find(x), y = find(y);if (x != y) fa[x] = y;
}
优化
优化1：启发式合并
如果不优化，时间复杂度可能会飙到 \(O(n)\)，就像可怜的二叉搜索树一样，怎么优化呢？平衡树
可以把子树节点少的连向节点多的，这样子，树高可以稳定在 \(\log_2 n\)。
期望复杂度：\(O(\log_2 n)\)。
优化2：路径压缩
我们只要知道代表元，我们可以将父亲直接连向代表元，这是非常大的优化，可以从 \(O(\log_2 n)\) 优化到 \(O(α(n))\)，\(α\) 是阿克曼反函数，可以当作不超过 \(4\) 的常数。
代码：
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
时间复杂度
优化1：启发式合并
期望复杂度：\(O(\log_2 n)\)。
实际复杂度：不知道。
优化2：路径压缩
期望复杂度：\(O(α(n))\)。
实际复杂度：不知道。
题外话
Tarjan 巨佬说："如果不用启发式合并，只用路径压缩，时间复杂度最坏也是 \(O(\log_2 n)\)，但均摊 \(O(α(n))\)。"
例题：
1. 并查集
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void unite(int x, int y) {x = find(x), y = find(y);if (x != y) {fa[x] = y;}
}
void solve() {n = read(), m = read();for (int i = 1; i <= n; i++) fa[i] = i;while (m--) {int op, x, y;op = read(), x = read(), y = read();if (op == 1) {unite(x, y);}else {printf("%c\n", find(x) == find(y) ? 'Y' : 'N');}}
}
2.资料分发 1
就是求连通分量个数。
void solve() {n = read(), m = read();for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= m; i++) {int x, y;x = read(), y = read();unite(x, y);}int res = 0;for (int i = 1; i <= n; i++)res += fa[i] == i;printf("%d\n", res); return 0;
}
3.连通图
就是求连通分量个数。
void solve() {n = read(), m = read();for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= m; i++) {int x, y;x = read(), y = read();unite(x, y);}int res = 0;for (int i = 1; i <= n; i++)res += fa[i] == i;printf("%d\n", res - 1); return 0;
}
4.朋友
map 来搞并查集。
map<int, int>fa;
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void unite(int x, int y) {x = find(x), y = find(y);if (x != y) {fa[x] = y;}
}
int main() {n = read(), m = read(), P = read(), Q = read();for (int i = -m; i <= n; i++) {fa[i] = i;}while (P--) {int x, y;x = read(), y = read();unite(x, y);}while (Q--) {int x, y;x = read(), y = read();unite(x, y);}int ans1 = 0, ans2 = 0;for (int i = -m; i <= -1; i++) {if (find(-1) == find(fa[i])) ans1++;}for (int i = 1; i <= n; i++)if (find(1) == find(fa[i])) ans2++;printf("%d\n", min(ans1, ans2));return 0;
}
5.营救
怎么这么像最小生成树呢？
int fa[N];
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void unite(int x, int y) {x = find(x), y = find(y);if (x != y) {fa[x] = y;}
}
int n, m, s, t;
vector<array<int, 3>> edges;
int main() {n = read(), m = read(), s = read(), t = read();edges.resize(m);for (int i = 0; i < m; i++) {scanf("%d%d%d", &edges[i][1], &edges[i][2], &edges[i][0]);}for (int i = 1; i <= n; i++) fa[i] = i;sort(edges.begin(), edges.end());for (auto [w, x, y] : edges) {int l = find(x), r = find(y);if (l != r)fa[l] = r;if (find(s) == find(t)) {printf("%d\n", w);return 0;}}return 0;
}
6. 炸铁路
暴力的没边了。
struct node {int u, v;
} e[N];
vector<pair<int, int>> ans;
int fa[N];
int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);
}
void unite(int x, int y) {x = find(x), y = find(y);if (x != y) {fa[x] = y;}
}
void solve(int x) {for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= m; i++) {if (i != x) {unite(e[i].u, e[i].v);}}for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {if (find(i) != find(j)) {ans.pb({e[x].u, e[x].v});return;}}}
}
int main() {n = read(), m = read();for (int i = 1; i <= m; i++) {int a, b;a = read(), b = read();e[++idx] = {a, b};}for (int i = 1; i <= m; i++) {solve(i);}sort(ans.begin(), ans.end());for (auto [x, y] : ans) {if (x > y) swap(x, y);printf("%d %d\n", x, y);}return 0;
}