河池市住房城乡建设网站,推广赚钱的微信小程序,福州专业网站建设网络公司,jsp网站开发环境配置【模板】并查集
题目描述
如题#xff0c;现在有一个并查集#xff0c;你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N , M N,M N,M ,表示共有 N N N 个元素和 M M M 个操作。
接下来 M M M 行#xff0c;每行包含三个整数 Z i , X i , Y i Z_i,X_i,Y…【模板】并查集
题目描述
如题现在有一个并查集你需要完成合并和查询操作。
输入格式
第一行包含两个整数 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 Zi,Xi,Yi 。
当 Z i 1 Z_i1 Zi1 时将 X i X_i Xi 与 Y i Y_i Yi 所在的集合合并。
当 Z i 2 Z_i2 Zi2 时输出 X i X_i Xi 与 Y i Y_i Yi 是否在同一集合内是的输出 Y 否则输出 N 。
输出格式
对于每一个 Z i 2 Z_i2 Zi2 的操作都有一行输出每行包含一个大写字母为 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 N \le 10 N≤10 M ≤ 20 M \le 20 M≤20。
对于 70 % 70\% 70% 的数据 N ≤ 100 N \le 100 N≤100 M ≤ 1 0 3 M \le 10^3 M≤103。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 4 1\le N \le 10^4 1≤N≤104 1 ≤ M ≤ 2 × 1 0 5 1\le M \le 2\times 10^5 1≤M≤2×105 1 ≤ X i , Y i ≤ N 1 \le X_i, Y_i \le N 1≤Xi,Yi≤N Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi∈{1,2}。 思路
首先定义一个大小为 N N N的数组pre用于记录每个元素的父节点。init函数用于初始化并查集使得每个元素的父节点都是自己。
root函数用于查找元素 x x x的根节点即在并查集中寻找 x x x所在集合的代表元素。这里采用路径压缩的方法即在查找过程中将 x x x到根节点的路径上的所有节点的父节点都直接设为根节点从而优化后续查找效率。
merge函数用于合并两个集合具体操作是找到两个元素的根节点如果根节点不同就将其中一个集合的根节点的父节点设置为另一个集合的根节点从而实现两个集合的合并。
check函数用于检查两个元素是否在同一集合中通过比较两个元素的根节点是否相同来判断。如果相同输出Y如果不同输出N。
在main函数中首先读取元素的数量 n n n和操作的数量 m m m然后进行初始化。接下来根据输入的操作类型进行合并或者检查操作。如果操作类型为1执行merge函数合并两个集合如果操作类型为2执行check函数检查两个元素是否在同一集合中。
使用路径压缩优化后代码运行用时大幅度缩短。但是路径压缩会破坏树形结构。 AC代码
#include iostream
#define AUTHOR HEX9CF
using namespace std;const int N 1e5 7;int pre[N];void init(int x) {for (int i 1; i x; i) {pre[i] i;}
}int root(int x) {int i x;while (pre[i] ! i) {i pre[i];}return pre[x] i;
}void merge(int x, int y) {x root(x);y root(y);if (x y) {return;}pre[x] y;
}void check(int x, int y) {x root(x);y root(y);if (x y) {printf(Y\n);} else {printf(N\n);}
}int main() {int n, m;scanf(%d %d, n, m);init(n);while (m--) {int z, x, y;scanf(%d %d %d, z, x, y);if (z 1) {merge(x, y);} else {check(x, y);}}return 0;
}
