【一百零六】【算法分析与设计】并查集的实现,P3367 【模板】并查集,sizee集合的元素个数信息-个人在线分享

并查集的实现

描述
给定一个没有重复值的整形数组arr，初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构，并提供以下两个操作。
boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
void union(int a, int b): 把a所在的集合与b所在的集合合并在一起，原本两个集合各自的元素以后都算作同一个集合
[要求]
如果调用isSameSet和union的总次数逼近或超过O(N)，请做到单次调用isSameSet或union方法的平均时间复杂度为O(1)
输入描述：
第一行两个整数N, M。分别表示数组大小、操作次数接下来M行，每行有一个整数opt 若opt = 1，后面有两个数x, y，表示查询(x, y)这两个数是否属于同一个集合若opt = 2，后面有两个数x, y，表示把x, y所在的集合合并在一起
输出描述：
对于每个opt = 1的操作，若为真则输出”Yes”，否则输出”No”
示例1
输入：
4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3
复制
输出：
No
Yes
Yes
复制
说明：
每次2操作后的集合为 ({1}, {2}, {3}, {4}) ({1}, {2, 3}, {4}) ({1, 2, 3}, {4})
备注：
1
⩽
N
,
M
⩽
1
0
6
1
⩽
N
,
M
⩽
1
0
6
1 \leqslant N, M \leqslant 10^6\1⩽N,M⩽10^6
$1 ⩽ N, M ⩽ 1 0^{6} 1 ⩽ N, M ⩽ 1 0^{6}$
保证$1 \leqslant x, y \leqslant $保证
1
⩽
x
,
y
⩽
N
1⩽x,y⩽N
$1 ⩽ x, y ⩽ N$

vector和map都是建立映射关系.

vector建立映射关系的要求是,下标必须从0开始,并且必须是数字.

unsigned int—>任意类型

map建立映射关系并没有这么多的要求.

任意类型—>任意类型

【一百零六】【算法分析与设计】并查集的实现,P3367 【模板】并查集,sizee集合的元素个数信息插图

#define debug // 定义调试宏
#ifdef debug // 如果定义了调试宏
#define o(x) #x<<"="<<(x)<<" " // 定义调试输出宏，输出变量名和值
#define bug(code) do{cout<<"L"<<__LINE__<<":";code;<<endl;}while(0) // 定义调试宏，在行号前输出调试信息
#else 
#define bug(code) do{}while(0) // 如果未定义调试宏，则定义空宏
#endif
#include // 引入所有标准库
using namespace std;
#define int long long // 定义 int 为 long long
#define endl '
' // 定义 endl 为换行符
#define _(i,a,b) for(int i=a;i<=b;i++) // 定义正向循环宏
#define _9(i,a,b) for(int i=a;i>=b;i--) // 定义反向循环宏
int n, m; // 定义全局变量 n 和 m
struct node { // 定义结构体 node
int op, x, y; // 包含三个整数成员 op, x 和 y
};
vector<node> readd; // 定义存储 node 的向量 readd
vector<int> father; // 定义存储父节点的向量 father
vector<int> sizee; // 定义存储集合大小的向量 sizee
/*
find递归函数,含义是返回i元素所在集合的代表元素下标.
内部逻辑保证father[i]的维护.
如果father[i]=i是代表元素不需要维护直接返回father[i].
如果father[i]!=i说明不是代表元素,需要维护father[i]
走一步,当前节点的代表元素下标=findd(father[i]).
*/
int findd(int i) { // 查找操作，带路径压缩
if(father[i] != i) father[i] = findd(father[i]); // 如果 i 不是自己的父节点，递归查找父节点
return father[i]; // 返回父节点
}
/*
合并操作,维护sizee和father
father[fx]=father[fy]
代表元素是fy,fx再也用不到了.所以需要维护fy代表元素的信息,即sizee信息.
*/
void unionn(int x, int y) { // 合并操作
int fx = findd(x), fy = findd(y); // 查找 x 和 y 的根节点
if(fx != fy) sizee[fy] += sizee[fx]; // 如果根节点不同，合并集合，更新大小
father[fx] = father[fy]; // 将 x 的根节点指向 y 的根节点
}
void solve() {
father.assign(n + 5, 0); // 初始化 father 向量，大小为 n+5，值为 0
sizee.assign(n + 5, 1); // 初始化 sizee 向量，大小为 n+5，值为 1
_(i, 1, n) father[i] = i; // 初始化每个节点的父节点为自己
for(auto& xx : readd) { // 遍历所有操作
int op = xx.op, x = xx.x, y = xx.y, fx = findd(x), fy = findd(y); // 获取操作类型和操作数，并查找根节点
if(op == 1) { // 如果操作类型为 1
if(fx == fy) cout << "Yes" << endl; // 如果 x 和 y 在同一个集合，输出 "Yes"
else cout << "No" << endl; // 否则输出 "No"
} else { // 如果操作类型为 0
unionn(x, y); // 合并 x 和 y 所在的集合
}
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 快速输入输出
cin >> n >> m; // 输入 n 和 m
_(i, 1, m) { // 循环 m 次
node tt; // 定义临时变量 tt
cin >> tt.op >> tt.x >> tt.y; // 输入操作类型和操作数
readd.push_back(tt); // 将操作存入 readd 向量
}
solve(); // 调用 solve 函数处理操作
}

P3367 【模板】并查集

【模板】并查集
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数
N
,
M
N,M
$N, M$ ,表示共有
N
N
$N$ 个元素和
M
M
$M$ 个操作。
接下来
M
M
$M$ 行，每行包含三个整数
Z
_
i
,
X
_
i
,
Y
_
i
Z\_i,X\_i,Y\_i
$Z_i, X_i, Y_i$ 。
当
Z
_
i
=
1
Z\_i=1
$Z_i = 1$ 时，将
X
_
i
X\_i
$X_i$ 与
Y
_
i
Y\_i
$Y_i$ 所在的集合合并。
当
Z
_
i
=
2
Z\_i=2
$Z_i = 2$ 时，输出
X
_
i
X\_i
$X_i$ 与
Y
_
i
Y\_i
$Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。
输出格式
对于每一个
Z
_
i
=
2
Z\_i=2
$Z_i = 2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
样例 #1
样例输入 #1
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
样例输出 #1
N
Y
N
Y
提示
对于
30
%
30\%
$30%$ 的数据，
N
≤
10
，
M
≤
2
N \le 10，M \le 2
$N \leq 10 ， M \leq 2$ 。
对于
70
%
70\%
$70%$ 的数据，
N
≤
100
，
M
≤
1
0
3
N \le 100，M \le 10^3
$N \leq 100 ， M \leq 1 0^{3}$ 。
对于
100
%
100\%
$100%$ 的数据，
1
≤
N
≤
1
0
4
1\le N \le 10^4
$1 \leq N \leq 1 0^{4}$ ，
1
≤
M
≤
2
×
1
0
5
1\le M \le 2 imes 10^5
$1 \leq M \leq 2 \times 1 0^{5}$ ，
1
≤
X
_
i
,
Y
_
i
≤
N
1 \le X\_i, Y\_i \le N
$1 \leq X_i, Y_i \leq N$ ，
Z
_
i
∈
{
1
,
2
}
Z\_i \in \{ 1, 2 \}
$Z_i∈{1,2}$ 。

#include // 引入所有标准库
using namespace std;
#define int long long // 定义 int 为 long long 类型
#define endl '
' // 定义 endl 为换行符
// 定义正向循环宏，步长为 k
#define _(i,a,b,k) for(int i=a;i<=b;i+=k)
// 定义反向循环宏，步长为 k
#define _9(i,a,b,k) for(int i=a;i>=b;i-=k)
int n, m; // 定义全局变量 n 和 m
struct node { // 定义结构体 node
int op, x, y; // 包含三个整数成员 op, x 和 y
};
vector<node> readd; // 定义存储 node 的向量 readd
vector<int> father; // 定义存储父节点的向量 father
vector<int> sizee; // 定义存储集合大小的向量 sizee
int findd(int i) { // 查找操作，带路径压缩
if (father[i] != i) father[i] = findd(father[i]); // 如果 i 不是自己的父节点，递归查找父节点
return father[i]; // 返回父节点
}
void unionn(int x, int y) { // 合并操作
int fx = findd(x), fy = findd(y); // 查找 x 和 y 的根节点
if (fx != fy) sizee[fy] += sizee[fx]; // 如果根节点不同，合并集合，更新大小
father[fx] = father[fy]; // 将 x 的根节点指向 y 的根节点
}
void solve() {
father.assign(n + 5, 0); // 初始化 father 向量，大小为 n+5，值为 0
sizee.assign(n + 5, 1); // 初始化 sizee 向量，大小为 n+5，值为 1
_(i, 1, n, 1) father[i] = i; // 初始化每个节点的父节点为自己
for (auto& xx : readd) { // 遍历所有操作
int op = xx.op, x = xx.x, y = xx.y; // 获取操作类型和操作数
if (op == 1) { // 如果操作类型为 1
unionn(x, y); // 合并 x 和 y 所在的集合
} else { // 如果操作类型为 0
if (findd(x) == findd(y)) cout << "Y" << endl; // 如果 x 和 y 在同一个集合，输出 "Y"
else cout << "N" << endl; // 否则输出 "N"
}
}
}
signed main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0); // 快速输入输出
cin >> n >> m; // 输入 n 和 m
_(i, 1, m, 1) { // 循环 m 次
node tt; // 定义临时变量 tt
cin >> tt.op >> tt.x >> tt.y; // 输入操作类型和操作数
readd.push_back(tt); // 将操作存入 readd 向量
}
solve(); // 调用 solve 函数处理操作
}

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

并查集的实现

P3367 【模板】并查集

结尾

admin 钻石

相关推荐