知识总结
并查集
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
并查集支持两种操作：
- 合并（Union）：合并两个元素所属集合（合并对应的树）。
- 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。
初始化
初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将每个结点的根结点就设成自己。
for(int i = 1; i <= n; i++)
a[i] = i;
查询 & 路径压缩
查询元素属于哪个集合需要沿着树向上移动，直至找到根节点。
而由于查询过程中经过的每个元素都属于该集合，我们可将其直接连到根节点以加快后续查询。
int a[maxn]; // a[i] 记录 i 所属的集合编号
int find(int x){ // 找 x 的集合编号
if(a[x] == x) return x; // x 就是本族老大，直接返回 x
else return a[x] = find(a[x]); // 往上找 a[x] 的老大，沿着路径更新 a[x] 所在集合编号
}
非递归版路径压缩
/*非递归版的 int find(int x) */
int find(int x){
int t = x; // t: 当前查询的结点
while(a[x] != x){ // 没到顶点
x = a[x]; // 一直找到顶点结束
}
// 路径压缩：沿着初始 x(t暂存) -> 顶点 x 都更新老大为 x
while(a[t] != t){
int s = a[t]; // s 暂存 t 的父亲（下个点）
a[t] = x; // 更新路径上每个点的老大为 x
t = s; // 更新当前点为 t 的父亲 s
}
return x;
}
合并
即合并两棵树，只需要将一棵树的根节点连到另一棵树的根节点。
int fx = find(x), fy = find(y); // fx: x 所属的集合编号， fy: y 所属的集合编号
if(fx != fy){ // 若不是同一个集合的
a[fx] = fy; // 合并 x 所在集合和 y 所在集合(用 y 的集合编号更新 x 的老大的集合编号)
}
典型例题
亲戚
思路
- 初始化每个节点就是自己所在族（集合）的老大。
- 根据输入亲戚关系进行集合的合并操作。
- 合并完成后查询所问两个元素的祖先结点（所在集合编号）是否相同。
代码
#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int a[maxn]; // a[i] 记录 i 的族号
int find(int x){ // 找 x 的族号
if(a[x] == x) return x; // x 就是本族老大，直接返回 x
else return a[x] = find(a[x]); // 往上找 a[x] 的老大，找到后更新 a[x]
}
int main(){
int n, m, p;
scanf("%d %d %d", &n, &m, &p);
for(int i = 1; i <= n; i++)
a[i] = i; // 先初始化单个人为一个族，族号为自己
int x, y;
while(m--){
scanf("%d %d", &x, &y);
int fx = find(x), fy = find(y); // fx: x 的族号， fy: y 的族号
if(fx != fy){ // 若不是同一族的
a[fx] = fy; // 合并 x 所在族和 y 所在族(用 y 的族号更新 x 族老大的族号)
}
}
while(p--){
scanf("%d %d", &x, &y);
if(find(x) == find(y)) // 查找 x 和 y 的族号进行匹配
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
村村通
思路
- 使用并查集记录集合总数 cnt，初始时 cnt = n，后面每合并两个集合 cnt–。
- 如果要想所有村都相通最后应该只有一个集合，因此用最后的集合数 cnt 减去 1 就是还需要连接的道路数。
代码
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int a[maxn];
int find(int x){
if(a[x] == x) return x;
return a[x] = find(a[x]);
}
int main(){
int n, m, x, y;
while(1){
scanf("%d", &n);
if(!n) return 0;
scanf("%d", &m);
for(int i = 1; i <= n; i++){
a[i] = i;
}
int cnt = n; // 初始集合总数为 n 个
while(m--){
scanf("%d %d", &x, &y);
int fx = find(x), fy = find(y);
if(fx != fy){
a[fx] = fy; // 合并两个集合
cnt--; // 集合总数减 1
}
}
printf("%d\n", cnt - 1); // 集合数 - 1 即为所需道路数
}
return 0;
}
木材仓库
思路
- 可以使用 STL 中的 set 来实现不同长度木材集合的维护。
- 使用 find(x) 在 set 中查询 x 是否存在，insert(x) 在 set 中插入新的 x，empty() 判断集合是否为空。
- 查找要取出的木棍，可以用 lower_bound(x) 查询 >= x 的最近元素地址，使用迭代器存其位置再去其前后值比较大小，求出最接近的，用 erase() 删除。
代码
#include <bits/stdc++.h>
using namespace std;
set<int> s;
int main(){
int n, op, len;
scanf("%d", &n);
while(n--){
scanf("%d %d", &op, &len);
if(op == 1){
if(s.find(len) != s.end()){
printf("Already Exist\n");
}
else{
s.insert(len);
}
}
else{
if(s.empty()){
printf("Empty\n");
}
else{ // 查找要取出的木棍
set<int>::iterator i = s.lower_bound(len), j = i;
if(j != s.begin()) j--; // 如果不是首地址，取前个位置
// (*j): 小于 x 最近的 (*i) : 大于等于 x 最近的
if(i != s.end()){ // 存在 >= x 的数，再进行 (*j) 和 (*i) 的比较
if(len - (*j) > (*i) - len){ // 后面的 (*i) 更佳
j = i; // j 存最佳元素的迭代器
}
}
printf("%d\n", (*j));
s.erase(j); // 取出位置 j 的木棍
}
}
}
return 0;
}
集合
思路
- 初始 [a, b] 中每个数一个集合，则可把集合总数初始化为 (b – a + 1)，后面每进行一次合并操作时，将集合数量减 1 即可。
- 用筛法筛出 b 以内所有的质数，枚举所有拥有公共质因数的数（即某个质因数的所有倍数），若这两个倍数在 [a, b] 范围中，且质因数大于等于 p，且两个数不属于同一集合，执行并查集合并操作，集合数量减 1。
- 最后输出合并完后的集合数就是答案。
代码
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int a, b, p, s, f[maxn];
bool prm[maxn];
int find(int x){
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
void is_prm(int b){
for(int i = 2; i <= b; i++){ // 遍历 b 以内所有可能的质数
if(!prm[i]){ // 是质数
for(int j = 2 * i; j <= b; j += i){
prm[j] = 1; // 把合数标记成 1
int f1 = find(j), f2 = find(j-i);
if(i >= p && j-i >= a && f1 != f2){
f[f1] = f2;
s--;
}
}
}
}
}
int main(){
scanf("%d %d %d", &a, &b, &p);
for(int i = a; i <= b; i++){
f[i] = i;
}
s = b - a + 1; // 初始的集合数
// 对 b 以内大于等于 p 的质因数，求出其 b 以内的所有倍数，合并到一个集合
is_prm(b);
cout << s;
return 0;
}
程序自动分析
思路
- 容易想到将所有可以相等的条件放在一个集合内，这样最后判断某个问题是否可被满足时，只需要看有没有不等的条件又属于同一个集合的，即非法情况，一旦出现一组，即可结束判断。
- 由于条件编号下标范围很大，直接用大数组是存不下的，因此首先需要对读入的若干约束条件进行离散化编码（映射到一个更小的数据范围），可以先将所有读到过的约束条件编号存入一个数组中，然后进行排序去重，再重新查找元素下标进行编号，这样编码范围最多 2 * n 个。
代码
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n, t, f[2 * maxn], b[maxn * 2];
struct node{
int x, y, e;
}a[maxn];
bool cmp(node a, node b){
return a.e > b.e; // 把 e 为 1 的操作先放前面统一处理
}
int find(int x){
if(f[x] == x) return x; // x 就是祖先，直接返回它的值
return f[x] = find(f[x]); // 用找到的 f[x] 的祖先更新 x 的爸爸
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
int s = 0; // 计数 X 条件个数
for(int i = 1; i <= n; i++){
scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].e);
b[s++] = a[i].x;
b[s++] = a[i].y;
}
sort(b, b + s); // 将条件排序
int k = unique(b, b + s) - b; // 更新去重后的元素个数
for(int i = 1; i <= n; i++){
a[i].x = lower_bound(b, b + k, a[i].x) - b; // 求出 a[i].x 离散化后的位置
a[i].y = lower_bound(b, b + k, a[i].y) - b; // 求出 a[i].x 离散化后的位置
}
// 并查集，合并相等的项到同一个集合
for(int i = 0; i < k; i++){
f[i] = i; // 先初始化 i 就是自己的爸爸
}
sort(a + 1, a + 1 + n, cmp); // 将 e = 1 的项排序在前面
bool flag = 1; // 假设条件都满足
for(int i = 1; i <= n; i++){
int fx = find(a[i].x), fy = find(a[i].y);
if(a[i].e){ // Xx = Xy 的情况
if(fx != fy){ // 若祖先不同
f[fx] = fy; // 合并到 fy 所在集合
}
}
else{ // Xx != Xy 的情况
if(fx == fy){ // 发现同属一个集合，不合理
flag = 0; // 标记非法
break; // 结束该组数据判断
}
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}