设计师常用网站,做拼团网站,网页设计介绍北京网站,f006网站建设【模板】并查集
题目描述
如题#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}。 思路
首先定义一个数组pre用于存储每个元素的父节点init函数用于初始化并查集使得每个元素的父节点都是其自身。
root函数用于查找元素的根节点也就是集合的代表元素通过不断地向上查找父节点直到找到一个元素的父节点是其自身那么这个元素就是根节点。
merge函数用于合并两个集合首先找到两个集合的根节点如果不在同一个集合即根节点不同就将其中一个集合的根节点的父节点设置为另一个集合的根节点这样就完成了两个集合的合并。
check函数用于检查两个元素是否在同一个集合只需要比较这两个元素的根节点是否相同即可。
在main函数中读取元素数量n和操作数量m然后初始化并查集。接着对每个操作进行处理如果操作类型z为1就调用merge函数合并两个元素所在的集合如果操作类型z为2就调用check函数检查两个元素是否在同一个集合。
注意要使用scanf和printf否则可能无法通过部分测试点。 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 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;
}
