【七十九】【算法分析与设计】并查集模板!!!并查集的实现_牛客题霸_牛客网,【模板】并查集

【七十九】【算法分析与设计】并查集模板!!!并查集的实现_牛客题霸_牛客网,【模板】并查集 - 洛谷,并查集代码!!!

并查集的实现_牛客题霸_牛客网

描述

给定一个没有重复值的整形数组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 \leqslant N, M \leqslant 10^61⩽N,M⩽106

保证1 \leqslant x, y \leqslant N保证1⩽x,y⩽N

递归转化为迭代,_find的递归写法转化为迭代的写法.

递归的出口是father[i]==i,所以while循环的入口在递归的出口条件前面加上一个!取反.

递归的进入下一层本来是_find(father[i]).转化为迭代就是i=father[i].

中间清理栈的迭代过程也可以想象成是递归的过程.

#include<bits/stdc++.h> // 引入常用的头文件
#define int long long // 定义int为长整型，以支持大数据量的处理
#define endl '\n' // 定义换行符为'\n'，增加输出速度
#define p pair< long long, long long> // 定义pair类型的别名p，用于存储两个长整型的数值using namespace std; // 使用标准命名空间const int dx[] = { 1, -1, 0, 0 }; // 定义数组dx，用于某些方向操作，此处可能未使用
const int dy[] = { 0, 0, 1, -1 }; // 定义数组dy，用于某些方向操作，此处可能未使用// 全局变量定义区域
int n, m; // n表示数组大小，m表示操作次数
int op, nums1, nums2; // op操作类型，nums1和nums2操作数vector<int> father; // 并查集数组，存储每个元素的父节点
vector<int> _stack; // 辅助栈，用于路径压缩int _find(int i) { // 并查集查找操作，带路径压缩while (!(father[i] == i)) { // 如果i不是自己的父节点，进行路径压缩i = father[i];_stack.push_back(i); // 将当前节点添加到栈中}while (_stack.size()) { // 当栈不为空时，进行路径压缩father[_stack.back()] = i; // 将栈中的每个元素的父节点设置为根节点i_stack.pop_back(); // 弹出栈顶元素}return i; // 返回根节点
}int isSameSet(int x, int y) { // 检查两个元素是否属于同一个集合return _find(x) == _find(y); // 通过查找根节点来判断
}void _union(int x, int y) { // 并查集合并操作if (_find(x) == _find(y)) { // 如果x和y已经属于同一个集合，则不操作return;} else {father[_find(x)] = _find(y); // 将x的根节点的父节点设置为y的根节点，完成合并}
}void init() { // 读取操作和操作数cin >> op >> nums1 >> nums2;
}void solveinit() { // 初始化解决方案，此处未使用
}void solve() { // 根据操作类型执行相应的并查集操作solveinit();if (op == 1) { // 如果是查询操作if (isSameSet(nums1, nums2))cout << "Yes" << endl; // 如果属于同一个集合，输出"Yes"else cout << "No" << endl; // 否则输出"No"} else { // 如果是合并操作_union(nums1, nums2); // 合并nums1和nums2所在的集合}
}signed main() { // 主函数ios::sync_with_stdio(false); // 禁用C和C++的同步，加速cin和coutcin.tie(nullptr); // 解除cin和cout的绑定cout.tie(nullptr);cout << fixed << setprecision(15); // 设置浮点数输出的精度cin >> n >> m; // 读入数组大小和操作次数father.assign(n + 1, 0); // 初始化father数组，大小为n+1for (int i = 0; i <= n; i++) { // 将每个元素的父节点初始化为自己father[i] = i;}while (m--) { // 读取m个操作并执行init();solve();}
}

【模板】并查集 - 洛谷

【模板】并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 $$N,$$ ,表示共有 $$$$ 个元素和 $$$$ 个操作。

接下来 $$$$ 行，每行包含三个整数 $$Z_i,X_i,Y_$$ 。

当 $$Z_i=$$ 时，将 $$X_$$ 与 $$Y_$$ 所在的集合合并。

当 $$Z_i=$$ 时，输出 $$X_$$ 与 $$Y_$$ 是否在同一集合内，是的输出

Y ；否则输出 N 。

输出格式

对于每一个 $$Z_i=$$ 的操作，都有一行输出，每行包含一个大写字母，为 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\$$ 的数据，$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 \}$。

#include<bits/stdc++.h> // 引入常用的头文件
#define int long long // 定义int为长整型，适用于处理大数据
#define endl '\n' // 定义结束符为'\n'，优化输出效率
#define p pair<long long, long long> // 定义pair的别名p，用于存储长整型的键值对using namespace std;const int dx[] = {1, -1, 0, 0}; // 方向数组，可能用于处理四方向问题，本代码未用到
const int dy[] = {0, 0, 1, -1}; // 方向数组，可能用于处理四方向问题，本代码未用到
//----------------------------------------------------int n, m; // n是元素数量，m是操作次数
int op, nums1, nums2; // op是操作类型，nums1和nums2是操作的元素vector<int> father; // 并查集的父节点数组
vector<int> _st; // 辅助栈，用于路径压缩int _find(int i) { // 查找根节点，并应用路径压缩while (!(father[i] == i)) { // 如果节点i不是自己的父节点，继续向上查找_st.push_back(i); // 将当前节点加入栈中i = father[i]; // 移动到父节点}while (_st.size()) { // 路径压缩，将路径上的所有节点直接连接到根节点father[_st.back()] = i;_st.pop_back();}return i; // 返回根节点
}bool isSameSet(int x, int y) { // 判断两个元素是否在同一集合中return _find(x) == _find(y);
}void _union(int x, int y) { // 合并两个集合if (_find(x) == _find(y)) { // 如果已经在同一集合中，则无需合并return;} else {father[_find(x)] = _find(y); // 否则，将一个集合的根节点指向另一个集合的根节点}
}// 初始化函数，读取输入并初始化并查集
void init() {cin >> n >> m;father.assign(n + 1, 0); // 分配并初始化并查集数组for (int i = 0; i <= n; i++) {father[i] = i; // 初始化时，每个元素的父节点是自己}
}// 根据操作类型执行相应的并查集操作
void solve() {if (op == 1) { // 如果是合并操作_union(nums1, nums2);} else { // 如果是查询操作if (isSameSet(nums1, nums2)) cout << "Y" << endl; // 如果在同一集合，输出Yelse cout << "N" << endl; // 否则输出N}
}signed main() {ios::sync_with_stdio(false); // 提高cin和cout的效率cin.tie(nullptr); // 解绑cin和coutcout.tie(nullptr);cout << fixed << setprecision(15); // 设置浮点数精度//----------------------------------------------init(); // 初始化while (m--) { // 处理每个操作cin >> op >> nums1 >> nums2;solve();}
}