深圳创建网站,网站建设与管理试卷_,网页设计宣传推广方案,贵州建筑工程网描述
给定 n n n个结点#xff0c; q q q次询问#xff0c;每次询问分为三类#xff1a;
1 x y #xff1a;可以选择将 x , y x, y x,y两个点连通#xff0c;如果已经连通则不操作。2 #xff1a;撤销上一次的操作#xff08;若全部撤销完了则不操作#xff09;。3 x…描述
给定 n n n个结点 q q q次询问每次询问分为三类
1 x y 可以选择将 x , y x, y x,y两个点连通如果已经连通则不操作。2 撤销上一次的操作若全部撤销完了则不操作。3 x y询问 x , y x, y x,y是否连通如果是则输出YES反之输出NO请注意都是大写字母不包含引号。
输入描述
第一行两个整数 n ( 1 ≤ n ≤ 1 0 6 ) , q ( 1 ≤ q ≤ 1 0 5 ) n (1 \leq n \leq 10^6), q (1 \leq q \leq 10^5) n(1≤n≤106),q(1≤q≤105)分别表示结点的个数和询问的次数。
接下来 q q q行每行一个询问op x y (1 \leq op \leq 3, 1 \leq x, y \leq n)当op2时没有 x , y x, y x,y。
输出描述
对于每一个3询问一行一个字符串“YES” 或 “NO”表示结果。
输入样例1
4 5
1 1 2
1 1 3
3 2 3
2
3 2 3输出样例1
YES
NO思路
在初始化函数init中遍历每个元素将其父节点设置为自己表示每个元素都是独立的集合同时集合的大小设置为1。
函数root负责查找元素的根节点。通过不断向上查找父节点直到找到一个元素的父节点是其自身即找到了该元素所在集合的根节点。
函数merge负责合并两个集合。首先查找两个元素的根节点如果根节点相同表示两个元素已经在同一集合中无需合并。否则将较小的集合并入较大的集合为了保证并查集的平衡性这里使用了按秩合并的策略。在合并的同时将合并的信息较小集合的根节点和较大集合的根节点压入栈s1以便后续进行撤销操作。
函数check负责检查两个元素是否在同一集合中。通过查找两个元素的根节点如果根节点相同表示两个元素在同一集合中输出YES否则表示两个元素不在同一集合中输出NO。
函数undo负责撤销最近的合并操作。从栈s1中弹出最近的合并信息将被合并的集合的根节点的父节点设置为其自身同时更新其父节点即原集合的大小恢复原来的集合状态。
在主函数中首先读取元素个数和操作次数然后进行初始化。然后根据操作类型进行相应的操作如果操作类型为2则进行撤销操作如果操作类型为1则进行合并操作如果操作类型为3则进行检查操作。 AC代码
#include algorithm
#include iostream
#include stack
#define AUTHOR HEX9CF
using namespace std;const int N 1e5 7;int pre[N], sz[N];
stackpairint, int s1;void init(int x) {for (int i 1; i x; i) {pre[i] i;sz[i] 1;}
}int root(int x) {int i x;while (pre[i] ^ i) {i pre[i];}return i;
}void merge(int x, int y) {int rx root(x);int ry root(y);if (rx ry) {return;}if (sz[rx] sz[ry]) {swap(rx, ry);}s1.push({rx, ry});pre[rx] ry;sz[ry] sz[rx];
}void check(int x, int y) {int rx root(x);int ry root(y);if (rx ry) {printf(YES\n);} else {printf(NO\n);}
}void undo() {if (s1.empty()) {return;}auto t s1.top();s1.pop();int rx t.first;int ry t.second;pre[rx] rx;sz[ry] - sz[rx];
}int main() {int n, m;scanf(%d %d, n, m);init(n);while (m--) {int opt;scanf(%d, opt);if (opt 2) {undo();} else {int a, b;scanf(%d %d, a, b);if (opt 1) {merge(a, b);} else {check(a, b);}}}return 0;
}
