扁平化小挂大~1.头文件和定义#includeiostream #includestack //使用栈实现路径压缩 using namespace std; const int N 2e5 10; int father[N]; // 父节点数组father[i]表示i的父节点 int siz[N]; // 集合大小数组siz[i]表示以i为根的集合大小 int n, m; // n:元素个数m:操作次数2.初始化void build() { for (int i 1;i n;i) // 遍历所有元素 { father[i] i; // 每个元素的父节点初始化为自己 siz[i] 1; // 每个集合初始大小为1 } }3.查找int find(int i) { stack int st; // 创建栈存储路径上的节点 // 第一步找到根节点同时记录路径 while (i ! father[i]) // 当i不是自己的父节点不是根 { st.push(i); // 将当前节点压入栈 i father[i]; // 向上移动到父节点 } // 此时i是根节点 // 第二步路径压缩扁平化 while (!st.empty()) // 当栈不为空 { int t st.top(); // 取出栈顶节点 father[t] i; // 将该节点的父节点直接指向根节点 st.pop(); // 弹出栈顶 } return i; // 返回根节点 }4.判断是否在同一集合bool is_same_set(int x, int y) { return find(x) find(y); // 比较两个元素的根节点是否相同 }5.合并bool Union(int x, int y) { int fx find(x); // 找到x的根 int fy find(y); // 找到y的根 if (fx ! fy) // 如果不在同一集合 { // 小挂大按秩合并 if (siz[fx] siz[fy]) // 如果fx的集合更大 { father[fy] fx; // 将fy挂到fx下 siz[fx] siz[fy]; // 更新fx的大小 } else // 如果fy的集合更大或相等 { father[fy] fx; siz[fy] siz[fx]; } return true; // 合并成功 } else return false; // 已经在同一集合无需合并 }6.主函数int main() { cin n m; // 读取元素个数和操作次数 build(); // 初始化并查集 while (m--) // 处理m个操作 { int opt 0; cin opt; // 操作类型1-合并2-查询 int x 0, y 0; cin x y; // 读取两个元素 if (opt 1) // 合并操作 Union(x, y); if (opt 2) // 查询操作 { if (is_same_set(x, y)) cout Y endl; // 在同一集合 else cout N endl; // 不在同一集合 } } return 0; }P3367 【模板】并查集题目背景本题数据范围已经更新到 1≤N≤2×1051≤M≤106。题目描述如题现在有一个并查集你需要完成合并和查询操作。输入格式第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。接下来 M 行每行包含三个整数 Zi​,Xi​,Yi​ 。当 Zi​1 时将 Xi​ 与 Yi​ 所在的集合合并。当 Zi​2 时输出 Xi​ 与 Yi​ 是否在同一集合内是的输出Y否则输出N。输出格式对于每一个 Zi​2 的操作都有一行输出每行包含一个大写字母为Y或者N。输入输出样例输入 #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说明/提示对于 15% 的数据N≤10M≤20。对于 35% 的数据N≤100M≤103。对于 50% 的数据1≤N≤1041≤M≤2×105。对于 100% 的数据1≤N≤2×1051≤M≤1061≤Xi​,Yi​≤NZi​∈{1,2}。#includeiostream #includestack using namespace std; const int N 2e5 10; int father[N]; int siz[N]; int n, m; void build() { for (int i 1;i n;i) { father[i] i; siz[i] 1; } } int find(int i) { stack int st; //扁平化 while (i ! father[i]) { st.push(i); i father[i]; } while (!st.empty()) { int t st.top(); father[t] i; st.pop(); } return i; } bool is_same_set(int x, int y) { return find(x) find(y); } bool Union(int x, int y) { int fx find(x); int fy find(y); if (fx ! fy) { //小挂大 if (siz[fx] siz[fy]) { father[fy] fx; siz[fx] siz[fy]; } else { father[fy] fx; siz[fy] siz[fx]; } return true; } else return false; } int main() { cin n m; build(); while (m--) { int opt 0; cin opt; int x 0, y 0; cin x y; if (opt 1) Union(x, y); if (opt 2) { if (is_same_set(x, y)) cout Y endl; else cout N endl; } } return 0; }