并查集 poj 2524,1611,1703,2236,2492,1988 练习集【蓝桥杯备赛】

前言

并查集优势

Ubiquitous Religions poj 2524

问题描述

问题分析

代码

The Suspects poj 1611

问题描述

问题分析

代码

Wireless Network poj 2236

问题描述

问题分析

代码

分类

带权并查集合

权值树构建步骤

Find them, Catch them poj 1703

问题描述

问题分析

代码

A Bug's Life poj 2492

分析

代码

Cube Stacking poj 1988

分析

代码

总结

前言

如果想看基础在这里并查集基础

并查集是一种极其轻巧的高级数据结构，在算法比赛中也较为常见，所以我们借几道题来加强一下。

并查集优势

在开始练习之前，我们先明确并查集究竟有什么用，为什么要用并查集：

并查集最本质的作用其实是在这个函数：

int find_set(int x) {if (x != s[x]) s[x] = find_set(s[x]);return s[x];
}

这个路径压缩算法可以使得集合中的任何一个元素都可以在O(1)的时间复杂度下找到其所属的集合。

根据这个优势我们就可以得出，并查集更善于解决集合类的问题

Ubiquitous Religions poj 2524

poj 2524

问题描述

想调查学校中学生的宗教信仰情况，但只知道两两同学之间是信仰相同宗教，问该学校中学生信仰的不同宗教的最大数量。

问题分析

这是一个恒明显的集合问题，具有相同宗教的同学属于一个集合，只需要将这些同学分好集合之后，统计并查集中有多少个集合即可。

这里其他代码都是并查集的原版代码，唯一需要注意的就是如何数并查集中的集合个数，在并查集中对于每个集合只有一个x有s[x]=x;我们可以根据这个特性，计数并查集中集合的个数

int ans = 0;
for (int i = 1; i <= n; i++) {if (s[i] == i) ans++;
}
cout <<"Case "<<k<<": " << ans << endl;
k++;

代码

#include<iostream>
using namespace std;
const int N = 320;
int s[N];void init_set() {for (int i = 1; i < N; i++) {s[i] = i;}
}int find_set(int x) {if (x != s[x]) s[x] = find_set(s[x]);return s[x];
}void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];}
}
int k = 1;
int main() {int  m, n, a, b;while (~scanf_s("%d%d", &n, &m) && (m || n)) {init_set();for (int i = 1; i <= m; i++) {cin >> a >> b;merge_set(a, b);}int ans = 0;for (int i = 1; i <= n; i++) {if (s[i] == i) ans++;}cout <<"Case "<<k<<": " << ans << endl;k++;}return 0;
}

The Suspects poj 1611

poj 1611

问题描述

一个学校有n名同学编号为0~n-1，m个社团，现已知编号为0的同学为感染者，如果和0号同学同属于一个社团那么也是感染者，和感染者同属于一个社团的同学也是感染者，先给出每个社团的人数以及社团同学编号，问这个学校有多少个感染者（不参加社团的同学不是感染者）。

问题分析

和上题一样这也是一个集合问题，和感染者同属于一个社团的同学都是感染者，我们把他们合并到一个集合中，最后在统计和编号为0同学同属于一个社团的人数。

但是这里需要注意一个易错点，就是由于只有进行了find_set(x)的元素才会进行路径压缩，所以并不是所有的S[X]都等于他所处的集合，也有可能还未更新，此时还在中间，所以在最后需要手动进行路径压缩，其实也不会耗费太多时间，因为此时的路径压缩已经距离根节点相当近了。

解释：

因为在merge_set(int a,int b)函数中我们只有一开始进行了find_set(x),也就是只有一开始进行了路径压缩，之后直接将roota接到了rootb上并没有将a也接到rootb上，所以需要手动将a接到rootb上，也就是再对a进行路径压缩

void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];}
}

代码

#include<iostream>
using namespace std;
const int N = 10005;
int s[N];void init_set() {for (int i = 0; i < N; i++) {s[i] = i;}
}int find_set(int x) {if (x != s[x]) s[x] = find_set(s[x]);return s[x];
}void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];}
}int main() {int n, m, t, head, a;while (cin >> n >> m && (n || m)) {init_set();for (int i = 1; i <= m; i++) {cin >> t;cin >> head;for (int j = 1; j < t; j++) {cin >> a;merge_set(a, head);}}int ss = find_set(0); //找到0所在的集合int ans = 0;for (int i = 0; i < n; i++) {find_set(i);  //手动路径压缩//cout << i << " :" << s[i] <<"  "<<s[s[i]] << endl;if (s[i] == ss) ans++;}cout << ans << endl;}
}

Wireless Network poj 2236

poj 2236

问题描述

有一些损坏的电脑，给出这些电脑的坐标，电脑之间距离超过某一值那么就无法接通，两相互接通的电脑之间允许通过几台电脑接通，电脑损坏也无法接通，先给出一些操作O a，代表修复编号为a的电脑，S a b代表查询a,b两台电脑是否联通

问题分析

这题很明显也是一个集合问题，我们可以把相互联通的电脑放在一个集合里，查询是否连通，只需要查询两台电脑是否属于一个集合即可，我们在修复电脑的操作时，需要遍历一遍所有修好的电脑，并将它们归到一个集合之中。

还有一个问题就是如何将电脑的编号和坐标存储，以便计算两电脑距离，这里我们是由一个结构体数组node[N],其中N代表电脑编号，node存储的信息有电脑坐标以及电脑是否修好。

代码

#include<iostream>
using namespace std;
const int N = 1005;int s[N];struct node {//暴力存点int x;int y;bool flag = false; //false代表这台计算机未被修复
}node[N];void init_set() {for (int i = 1; i < N; i++) {s[i] = i;}
}int find_set(int x) {if (x != s[x]) s[x] = find_set(s[x]);return s[x];
}void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];}
}double cal_dis(int a, int b) {double x = (node[a].x - node[b].x) * (node[a].x - node[b].x);double y = (node[a].y - node[b].y) * (node[a].y - node[b].y);// cout << y << endl;return sqrt(x + y);
}int main() {int n;double d;cin >> n >> d;init_set();for (int i = 1; i <= n; i++) {cin >> node[i].x >> node[i].y;}char c;int a, b;while (cin >> c) {if (c == 'O') {cin >> a;node[a].flag = true;//暴力遍历,每输入一个已经修好的电脑，就遍历一遍所有的电脑，判断一下是否联通for (int i = 1; i <= n; i++) {if (node[i].flag == true) {double dis = cal_dis(a, i);//如果满足距离要求说明是联通的if (dis <= d) merge_set(i,a);}}}if (c == 'S') {cin >> a >> b;int roota = find_set(a), rootb = find_set(b);if (roota == rootb) {cout << "SUCCESS" << endl;}else cout << "FAIL" << endl;}}
}

分类

以上的题目都是并查集的第一个应用，分类，无论是第一个题目判断有几个宗教，还是第二个题目感染者，这本质上都是分类问题，而分类最难的也就是需要知道他所属于哪个集合，由于并查集可以快速找到元素所属的集合所以在合并的过程中就显得极其迅速，从而加速了分类操作速度。

带权并查集合

怎么说呢，其实这完全是属于利用并查集可以快速找到元素所属集合的一个应用，本质上已经不是一个集合问题了，更像是利用路径压缩以及权值更新创建的一棵大部分是叶子节点（有些节点在merge_set操作之后还未路径压缩）的高效权值树。

权值树构建步骤

这里只讲和普通并查集不同的地方，其他都按照并查集模板来。

（1）初始化每个节点的权值，如果是距离一般会初始化为0，这需要根据实际情况选择，一般就是0或1.

int find_set(int x) {if (x != s[x]) {int t = s[x];  //注意这里的d[t]和下面的d[t]是不一样的，这里的d[t]还未更新s[x] = find_set(s[x]);/*if (d[x] && d[t]) {if (d[x] == d[t]) d[x] = 1;else d[x] = -1;}else d[x] = 0;*///效果和上面代码一样，纯属个人喜好d[x] = link_set(d[x], d[t], 1);}return s[x];
}

（2）在路径压缩过程中更新权值，因为在路径压缩过程中，在一整条路径上的节点所属的集合都合并到了根集合，那么同样的也需要更新权值。

更新权值的方式用很多中，但本质上都是更新其与根节点的关系，这个关系可以是距离，方位，是否属于一个集合（别惊讶，上面已经说过，带权并查集本质上已经不是并查集了）。

但其实这里的更新方式是由一定方法的，想要理解这里的更新方式，就需要了解find_set函数在运行过程中干了什么。

这是一个递归的过程，直到找到x满足x=s[x]，那么返回是s[x]（为便于理解，下文假设s[x]=set）,那么在回溯的过程中就会把set赋值给沿路上的每一个s[x]。

这就是find_set的全过程，我们现在来分析要更新d[x],我们已知什么，首先未更新前的的d[x]我们是已知的，原来的d[x]代表x与进行路径压缩前的根节点的关系，这个好理解，一开始x的根节点就是自身，如果这个算法是正确的，那么随着路径压缩根节点也会更新最终得到d[x]，在之后就是d[s[x]]也是已知的,这个不大好理解，但你可以想象当find_set算法开始回溯时：

我们要求d[x],
由于此时的d[x]=x,
那么d[x]和d[s[x]]其实是相同的那么初始时这个算法是可行的
此时的d[s[x]]代表的是x更新前的根节点(s[x])与整个集合根节点的关系，此时利用d[x]和d[s[x]]这两个关系，
就可以成功更新d[x],把d[x]更新为x与整个集合根节点的关系，
那么类推s[t]=x的话，那么d[t]已知，d[s[t]]=d[x]已知
也可以把d[t]更新为t与整个集合根节点的关系

void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];/*if (d[a] && d[b]) {if (d[a] == d[b]) d[roota] = -1;else d[roota] = 1;}else d[roota] = 0;*///效果和上面代码一样，纯属个人喜好d[roota] = link_set(d[a], d[b], -1);}
}

（3）还有一个需要更新权值的地方就是merge_set（int a,int b,int m）操作，因为在合并操作时会将s[roota]接到s[rootb]上，此时就需要更新d[roota],多嘴一句注意的地方，这里只更新了d[roota]如果需要更新roota下的其他节点，需要额外进行路径压缩，因为此时新接到s[rootb]上的节点只有roota，这也就解释了The Suspects这题。这里我们直接上图：

已知a->b关系为v，a->roota关系为m
那么就可以推出b->roota的关系k
已知b->roota关系k,b->rootb关系l
那么就可推出roota->rootb关系h

int roota = find_set(a), rootb = find_set(b);
if (roota == rootb) {int end = link_set(d[a], d[b],1);if(end==1) cout << "In the same gang." << endl;if(end==-1) cout << "In different gangs." << endl;else cout << "Not sure yet." << endl;//效果和上面代码一样，纯属个人喜好/*if (d[a] && d[b]) {if (d[a] == d[b]) cout << "In the same gang." << endl;else cout << "In different gangs." << endl;}else cout << "Not sure yet." << endl;*/
}
//如果关系输完了根节点任然不一样，那么证明这两个集合间没有任何关系，所以无法推得a，b关系
else {cout << "Not sure yet." << endl;
}

（4）接下来就是如果给出a->b关系且此时roota=rootb那么就可以判断给出的a->关系是否正确：

Find them, Catch them poj 1703

poj 1703

问题描述

给出一些关系和一些查询，每个查询根据已有的关系输出结果，关系的格式为 D a b 代表a，

b这两个人不属于一个帮派。

问题分析

如果关系表示为a，b属于一个帮派，那么这个就是妥妥的一个并查集基础应用，这里表示的是a，b不属于一个集合，但归根结底这题还是个集合问题，那么我们优先考虑的还是并查集，因为并查集有一个特别好的优点就是可以迅速找到元素所属的集合。既然不能用并查集的分类功能，那么就考虑用并查集建立一棵权值树。

就根据上文给出的三步逐步编写代码即可

代码

#include<iostream>
using namespace std;const int N = 1*10e5 + 5;int s[N];
int d[N];//带权并查集 规定：
//1：代表（a,b)属于一个集合
//-1代表（a，b）不属于一个集合
//0: 代表（a,b)关系未知 void init_set() {for (int i = 1; i <= N - 1; i++) {s[i] = i;d[i] = 1;  //初始化，根节点是自己，自然是属于同一集合，初始化为1}
}int link_set(int a, int b,int c) {if (a && b) {if (a == b)  return 1*c;else return -1*c;}else return 0;
}int find_set(int x) {if (x != s[x]) {int t = s[x];s[x] = find_set(s[x]);/*if (d[x] && d[t]) {if (d[x] == d[t]) d[x] = 1;else d[x] = -1;}else d[x] = 0;*///效果和上面代码一样，纯属个人喜好d[x] = link_set(d[x], d[t], 1);}return s[x];
}void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];/*if (d[a] && d[b]) {if (d[a] == d[b]) d[roota] = -1;else d[roota] = 1;}else d[roota] = 0;*///效果和上面代码一样，纯属个人喜好d[roota] = link_set(d[a], d[b], -1);}
}int main() {int t,n,m,a, b;char c;cin >> t;while (t--) {init_set();cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> c;cin >> a >> b;if (c == 'A') {int roota = find_set(a), rootb = find_set(b);if (roota == rootb) {int end = link_set(d[a], d[b],1);if(end==1) cout << "In the same gang." << endl;if(end==-1) cout << "In different gangs." << endl;else cout << "Not sure yet." << endl;//效果和上面代码一样，纯属个人喜好/*if (d[a] && d[b]) {if (d[a] == d[b]) cout << "In the same gang." << endl;else cout << "In different gangs." << endl;}else cout << "Not sure yet." << endl;*/}//如果关系输完了根节点任然不一样，那么证明这两个集合间没有任何关系，所以无法推得a，b关系else {cout << "Not sure yet." << endl;}}if (c == 'D') {merge_set(a, b); }}}
}

之后的代码就大差不差了，不多解释

A Bug's Life poj 2492

poj 2492

分析

代码

#include<iostream>
using namespace std;const int N = 2005;int s[N];
int d[N];
int flag = 0;//规定：
//1：代表同性
//0：代表异性
void init_set() {for (int i = 1; i < N; i++) {s[i] = i;d[i] = 1;  //表示与i与i所属的根节点的关系}flag = 0; //顺便把flag也初始化了
}//下面这三个办法效果都一样，后两种利用了一点离散数学的知识
int cal_relation1(int a, int b) {return a == b;
}int cal_relation2(int a, int b) {return ~(a ^ b) & 1;
}int cal_relation3(int a, int b) {return !(!(a && b) && !(!a && !b));
}int find_set(int x) {if (x != s[x]) {int t = s[x];s[x] = find_set(s[x]);d[x] = cal_relation1(d[t], d[x]);}return s[x];
}void merge_set(int a, int b) {int roota = find_set(a), rootb = find_set(b);if (roota != rootb) {s[roota] = s[rootb];d[roota] = cal_relation1(cal_relation2(d[a], 0), d[b]);}else {int c = cal_relation3(d[a], d[b]);if (c == 1) {flag = 1;}}
}int main() {int t,n,m,a,b;cin >> t;for (int j = 1; j <= t; j++) {init_set();cin >> n >> m;for (int i = 1; i <= m; i++) {cin >> a >> b;merge_set(a, b);}cout << "Scenario #" << j << ":" << endl;if (flag == 1) cout << "Suspicious bugs found!" << endl;else cout << "No suspicious bugs found!" << endl;}
}

Cube Stacking poj 1988

poj 1988

分析

本题需要注意的是我们利用了一个cnt辅助数组存储每个集合中元素的个数

代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
using namespace std;#define maxn 30005
int s[maxn], d[maxn], cnt[maxn]; //d【i】数组记录的是i节点下有几个立方体void init_set(int n)
{for (int i = 1; i <= n; i++){s[i] = i, d[i] = 0, cnt[i] = 1;}
}int find_set(int x)
{if (s[x] != x) {int t = s[x];s[x] = find_set(s[x]);d[x] += d[t];//由于路径压缩并不会改变同一个集合元素的数量，所以这里不更新cnt}return s[x];
}void merge_set(int x, int y)
{x = find_set(x), y = find_set(y);if (x != y) {s[x] = y;d[x] += cnt[y];cnt[y] += cnt[x]; //合并操作时更新}
}int main()
{int p;while (~scanf("%d", &p)){init_set(maxn - 1);while (p--){char op;scanf_s(" %c", &op);if (op == 'M'){int x, y;scanf_s("%d%d", &x, &y);merge_set(x, y);}else{int x;scanf_s("%d", &x);find_set(x);printf("%d\n", d[x]);}}}return 0;
}