企业官网建设流程全解析

网站推广的重要性,零基础学网站建设 知乎,skycc营销软件,wordpress 数字格式题目背景本题数据范围已经更新到 1≤N≤2105#xff0c;1≤M≤106。题目描述如题#xff0c;现在有一个并查集#xff0c;你需要完成合并和查询操作。输入格式第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。接下来 M 行#xff0c;每行包含三个整数 Zi​,Xi​,Yi…题目背景本题数据范围已经更新到 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}。【算法模板】并查集 (Union-Find)路径压缩与集合合并1. 核心概念并查集是一种用于管理元素所属集合的数据结构主要支持两种操作合并Union将两个不同的集合合并为一个集合。查询Find查询某个元素属于哪个集合即寻找该集合的“代表”或“老大”。通俗理解数组fa[i]记录第i个人的“上级”是谁。初始化刚开始每个人都是自己的老大 (fa[i] i)。查询 (find)想知道你是哪个帮派的就一级一级往上找直到找到那个“上级是自己”的人他就是帮主。路径压缩找帮主太累了一旦找到帮主直接把你的上级改成帮主。以后再问一步就能找到。合并 (uni)两个帮派要合并让 A 帮派的帮主认 B 帮派的帮主做老大。2. 完整代码#include bits/stdc.h using namespace std; int n,m,z,x,y; int fa[200010];//记录每个节点的父节点 即所在集合的老大 //找老大的过程中进行路径压缩 //即找到x的祖宗节点并在过程中将x到祖宗路径上所有点的父节点直接设为祖宗 int find(int x){ if(fa[x]x) return x;//如果自己就是自己老大返回自己 //这一行完成了在查询过程中进行路径压缩 将最终的老大赋给到路径上每一个元素 else return fa[x]find(fa[x]); } void uni(int x,int y){ int faxfind(x); int fayfind(y); //如果x和y老大不同 就要合并 让x的老大变成y的老大的老大 if(fax!fay) fa[fay]fax; } int main(){ ios::sync_with_stdio(false); cin.tie(0); //初始化所有元素的老大是自己 cinnm; for(int i1;in;i) fa[i]i; while(m--){ cinzxy; if(z1){//合并 uni(x,y); } else if(z2){//查询 //\n代替endl输出更快 if(find(x)find(y)) coutY\n; else coutN\n; } } }3. 关键细节解析A. 路径压缩return fa[x]find(fa[x]);这行代码是并查集效率极高的关键。如果不加这一步树可能会退化成一条长链查询复杂度变成 O(N)。加上路径压缩后每次查询都会“压扁”树的高度平均时间复杂度接近O(1)准确说是反阿克曼函数 O((N))。B. 初始化的时机很多新手包括以前的我容易犯的错误// ❌ 错误写法 for(int i1; in; i) fa[i]i; // 此时 n 还是 0 cin n m; // ✅ 正确写法 cin n m; // 先读入 n for(int i1; in; i) fa[i]i; // 再根据 n 初始化如果顺序反了fa数组全是 0后续的find操作会陷入死循环或访问越界。C. 输出优化在算法竞赛中当输出行数非常多例如10^5行时coutendl会强制刷新缓冲区速度慢。cout \n仅换行速度快。建议习惯性使用 \n。4. 应用场景并查集不仅用于判断连通性还是很多高级算法的基石图论判环加边时如果两个点已经在一个集合里说明形成了环。Kruskal 算法最小生成树的核心利用并查集判断边是否连接了两个不同的连通块。连通块数量统计最后遍历一遍fa数组统计fa[i]i的个数。