一点废话
1.为什么会学并查集
因为训练赛卡了一道并查集的题(悲,更致命的是咱明知是并查集但因为连板子都抄不明白所以emmm
2.并查集在什么时候使用
a.将几个元素归类,或者说成组,求某元素是否属于某一组
b.将几个元素归类,询问任意两个元素是否属于同一集合
c.按照某种关系将不同元素各自归类,询问至少分几个组
3.并查集的缺点
详情见并查集复杂度 - OI Wiki (oi-wiki.org)
TLETLETLE
正文
简介
并查集是一种树形的数据结构,顾名思义,它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作:
- 查找(Find):确定某个元素处于哪个子集;
- 合并(Union):将两个子集合并成一个集合。
需要注意的是并查集不支持拆分
*并查集的本质是找两个元素之间有无公共祖先来判定关系
板子
开门见山,直接放板子
◍ 查找(Find):确定某个元素处于哪个子集;
'cpp'
int find(int x) {
if (x != f[x]) // x 不是自身的父亲,即 x 不是该集合的代表
f[x] = find(f[x]); // 查找 x 的祖先直到找到代表,于是顺手路径压缩
return f[x];
}
◍ 合并(Union):将两个子集合并成一个集合。
'cpp'
void Union(int x ,int y){
int a = find(x), b = find(y);//分别查询a于b的公共祖先
f[a] = find(b);//这一步很关键,这一步就是将两个元素合并到同一个集合(表明两个元素之间是否有联系)
//将a合并为b本质上就是f[a]即a元素的祖先等于b元素的祖先,那么两个元素的公共祖先相等,因此处于同一个集合中
}
◍ 查询 (inquire) : 查询两个元素之间是否有关联(两个元素是否存在于同一个集合里)。
'cpp'
void inquire(int x,int y){
int a = find(x), b = find(y);//分别查询a于b的公共祖先
if(a==b){//如果a于b的公共祖先是同一个,那么这两个元素就存在于同一个集合中
cout<<"a与b存在于同个数组中"<<endl;
}
else if(a!=b){
cout<<"a与b并不存在于同个数组"<<endl;
}
}
题来
1.模板题
a.【模板】并查集 - 洛谷
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行,每行包含三个整数 Z_i,X_i,Y_i 。
当 Z_i=1 时,将 X_i 与 Y_i 所在的集合合并。
当 Z_i=2 时,输出 X_i 与 Y_i 是否在同一集合内,是的输出 Y
;否则输出 N
。
输出格式
对于每一个 Z_i=2 的操作,都有一行输出,每行包含一个大写字母,为 Y
或者 N
。
样例 #1
样例输入 #1
'math'
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
样例输出 #1
'math'
N
Y
N
Y
提示
对于 30\% 的数据,N \le 10,M \le 20。
对于 70\% 的数据,N \le 100,M \le 10^3。
对于 100\% 的数据,1\le N \le 10^4,1\le M \le 2\times 10^5,1 \le X_i, Y_i \le N,Z_i \in \{ 1, 2 \}。
题解
直接对着板子抄,非常的容易
'cpp'
#include <bits/stdc++.h>
using namespace std;
const int maxn=200010;
typedef long long ll;
int f[maxn];
int vis[30];
int find(int x) {
if (x != f[x]) // x 不是自身的父亲,即 x 不是该集合的代表
f[x] = find(f[x]); // 查找 x 的祖先直到找到代表,于是顺手路径压缩
return f[x];
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
f[i] = i;
}
while (m--) {
int cmd, x, y;
cin >> cmd >> x >> y;
int a = find(x), b = find(y);
if (cmd == 1) {
f[a] = find(b);
}
else {
if (a == b) {
cout << "Y" << endl;
}
else {
cout << "N" << endl;
}
}
}
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}
b.村村通 - 洛谷
题目描述
某市调查城镇交通状况,得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要相互之间可达即可)。请你计算出最少还需要建设多少条道路?
输入格式
输入包含若干组测试数据,每组测试数据的第一行给出两个用空格隔开的正整数,分别是城镇数目 n 和道路数目 m ;随后的 m 行对应 m 条道路,每行给出一对用空格隔开的正整数,分别是该条道路直接相连的两个城镇的编号。简单起见,城镇从 1 到 n 编号。
注意:两个城市间可以有多条道路相通。
输出格式
对于每组数据,对应一行一个整数。表示最少还需要建设的道路数目。
样例 #1
样例输入 #1
'math'
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
样例输出 #1
'math'
1
0
2
998
提示
数据规模与约定
对于 100% 的数据,保证 1 \le n < 1000 。
题解
这题需要套注意的是要保证新插入的两个元素的祖先不是同个祖先的前提下对两个元素进行合并
'cpp'
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int fa[5010];
int ans[10086];
int n, m, p, x, y;
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void Union(int x, int y) {
int a = find(x), b = find(y);
if (a != b)fa[a] = find(b);//这一步很关键,这一步就是将两个元素合并到同一个数组(表明两个元素之间是否有联系)
}
int main()
{
int cnt = 1;
while (cin >> n) {
int ans = 0;
if (n == 0) return 0;
cin >> m;
int cnt = 0;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
cin >> x >> y;
Union(x, y);
}
for (int i = 1; i <= n; i++) {
if (find(i) == i) ans++;
}
cout << ans - 1 << endl;
}
return 0;
}
2.模板题
为什么是模板题呢因为本质上所有并查集的题目都是在套模板(暴论)
还记得前文训练赛遇到的并查集题目吗,本质上就是个二维并查集
1.Mr. Kitayuta's Colorful Graph
题目描述
Mr. Kitayuta has just bought an undirected graph consisting of n vertices and m edges. The vertices of the graph are numbered from 1 to n . Each edge, namely edge i , has a color c_{i} , connecting vertex a_{i} and b_{i} .
Mr. Kitayuta wants you to process the following q queries.
In the i -th query, he gives you two integers — u_{i} and v_{i} .
Find the number of the colors that satisfy the following condition: the edges of that color connect vertex u_{i} and vertex v_{i} directly or indirectly.
输入格式
The first line of the input contains space-separated two integers — n and m ( 2<=n<=100,1<=m<=100 ), denoting the number of the vertices and the number of the edges, respectively.
The next m lines contain space-separated three integers — a_{i} , b_{i} (1 ≤ a_{i}< b_{i} ≤ n) and c_{i} ( 1<=c_{i}<=m ). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if i≠j , (a_{i},b_{i},c_{i})≠(a_{j},b_{j},c_{j}) .
The next line contains a integer — q ( 1<=q<=100 ), denoting the number of the queries.
Then follows q lines, containing space-separated two integers — u_{i} and v_{i} ( 1<=u_{i},v_{i}<=n ). It is guaranteed that u_{i}≠v_{i} .
输出格式
For each query, print the answer in a separate line.
样例 #1
样例输入 #1
'math'
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4
样例输出 #1
'math'
2
1
0
样例 #2
样例输入 #2
'math'
5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4
样例输出 #2
'math'
1
1
1
1
2
提示
Let's consider the first sample.
- The figure above shows the first sample. - Vertex 1 and vertex 2 are connected by color 1 and 2 .
- Vertex 3 and vertex 4 are connected by color 3 .
- Vertex 1 and vertex 4 are not connected by any single color.
题解
只是开个二维,本质还是并查集
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=110;
typedef long long ll;
int f[maxn];
int vis[30];
int fa[maxn][maxn];
map<string, int>maps;
int find(int x,int round) {
if (x != fa[x][round]) // x 不是自身的父亲,即 x 不是该集合的代表
fa[x][round] = find(fa[x][round],round); // 查找 x 的祖先直到找到代表,于是顺手路径压缩
return fa[x][round];
}
void solve() {
int n, m;
cin >> n >> m;
for (int j = 1; j <= 100; j++) {//初始化
for (int i = 1; i <= 100; i++) {
fa[i][j] = i;
}
}
while(m--) {
int x, y, z;
cin >> x >> y >> z;
int a = find(x, z);
int b = find(y, z);
fa[a][z] = find(b,z);
}
cin >> m;
while (m--) {
int x, y;
cin >> x >> y;
int cnt = 0;
for (int i = 1; i <= 100; i++) {
int a = find(x, i);
int b = find(y, i);
if (a == b) cnt++;
}
cout << cnt << endl;
}
return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}
未完,之后遇到的一些罕见还会持续更新
3.几个参考
算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)
并查集复杂度 - OI Wiki (oi-wiki.org)(虽然说并查集有诸多优点,但也容易TLE)
并查集详解 - Nemlit 的博客 - 洛谷博客 (luogu.com.cn)(版题的题解,看懂就能写并查集了)
Comments NOTHING