古蔺中国建设银行网站python如何做简单的网站

古蔺中国建设银行网站,python如何做简单的网站,wordpress 知更鸟 网格,上海市建设工程咨询行业协会官网什么是并查集 并查集是一种用于处理不相交集合的数据结构#xff0c;主要支持两种操作#xff1a; Union#xff08;合并#xff09;#xff1a;将两个集合合并为一个集合Find#xff08;查找#xff09;#xff1a;判断某个元素属于哪个集合 并查集特别适合解决连通性…什么是并查集并查集是一种用于处理不相交集合的数据结构主要支持两种操作Union合并将两个集合合并为一个集合Find查找判断某个元素属于哪个集合并查集特别适合解决连通性问题例如判断两个元素是否在同一个集合中。并查集的基本实现核心数据结构typeUnionFindstruct{parent[]int// parent[i] 表示元素 i 的父节点rank[]int// rank[i] 表示以 i 为根的树的高度用于按秩合并}三个核心操作1. 初始化每个元素初始时都是独立的集合自己是自己的父节点。funcNewUnionFind(nint)*UnionFind{parent:make([]int,n)rank:make([]int,n)fori:0;in;i{parent[i]i// 初始时自己是自己的父节点rank[i]1}returnUnionFind{parent:parent,rank:rank}}2. Find查找- 路径压缩优化查找元素的根节点同时进行路径压缩将路径上的所有节点直接连到根节点。func(uf*UnionFind)Find(xint)int{ifuf.parent[x]!x{uf.parent[x]uf.Find(uf.parent[x])// 路径压缩}returnuf.parent[x]}路径压缩的作用将树的高度降低后续操作更快。时间复杂度接近 O(1)。3. Union合并- 按秩合并优化将两个集合合并优先将高度小的树合并到高度大的树下。func(uf*UnionFind)Union(x,yint){rootX:uf.Find(x)rootY:uf.Find(y)ifrootXrootY{return// 已经在同一集合}// 按秩合并将高度小的树连到高度大的树下ifuf.rank[rootX]uf.rank[rootY]{uf.parent[rootX]rootY}elseifuf.rank[rootX]uf.rank[rootY]{uf.parent[rootY]rootX}else{uf.parent[rootY]rootX uf.rank[rootX]}}按秩合并的作用避免树退化成链表保持树的平衡。辅助方法// 判断两个元素是否连通func(uf*UnionFind)IsConnected(x,yint)bool{returnuf.Find(x)uf.Find(y)}// 重置节点某些场景需要func(uf*UnionFind)Reset(xint){uf.parent[x]x uf.rank[x]1}并查集的应用场景1. 判断连通性网络连接朋友圈问题岛屿数量2. 动态连通性判断图中是否存在环最小生成树Kruskal 算法3. 分组/聚类账户合并社交网络分析4. 带时间维度的连通性本题需要按时间顺序处理可能需要回退/重置操作并查集常见套路套路1基础连通性判断uf:NewUnionFind(n)// 建立连接uf.Union(x,y)// 判断连通ifuf.IsConnected(a,b){// 处理逻辑}套路2统计集合数量通过统计有多少个根节点来确定集合数量。count:0fori:0;in;i{ifuf.Find(i)i{count}}套路3带权并查集维护节点间的关系距离、差值等。套路4时间维度处理按时间排序分时间段处理需要时进行回退复杂度分析使用路径压缩和按秩合并优化后单次操作时间复杂度O(α(n))α 是阿克曼函数的反函数增长极慢实际可看作 O(1)空间复杂度O(n)实战案例LeetCode 2092. 找出知晓秘密的所有专家题目描述给定 n 个专家编号 0 到 n-1一个会议列表 meetings[i] [xi, yi, timei]以及初始知道秘密的 firstPerson。专家 0 在时间 0 时知道秘密并分享给 firstPerson每次会议时知道秘密的专家会分享给对方同一时间的秘密传播是瞬时的返回所有最终知道秘密的专家列表解题分析这是一道带时间维度的并查集问题体现了套路4的应用。核心难点时间维度需要按时间顺序处理会议同时刻处理同一时刻的会议必须一起处理瞬时传播回退机制如果某人没有连通到专家0需要撤销其加入解题步骤初始化将专家 0 和 firstPerson 合并到同一集合按时间排序将所有会议按时间升序排列分时间段处理收集同一时刻的所有会议对这些会议进行 Union 操作检查参会者是否与专家 0 连通关键不连通的参会者需要 Reset回退收集结果统计所有与专家 0 连通的专家代码实现funcfindAllPeople(nint,meetings[][]int,firstPersonint)[]int{uf:NewUnionFind(n)uf.Union(0,firstPerson)// 按时间排序sort.Slice(meetings,func(i,jint)bool{returnmeetings[i][2]meetings[j][2]})// 按时间分组处理i:0forilen(meetings){currentTime:meetings[i][2]peopleInMeetings:make(map[int]bool)// 处理同一时间的所有会议j:iforjlen(meetings)meetings[j][2]currentTime{x,y:meetings[j][0],meetings[j][1]uf.Union(x,y)peopleInMeetings[x]truepeopleInMeetings[y]truej}// 回退不连通的参会者需要重置forperson:rangepeopleInMeetings{if!uf.IsConnected(person,0){uf.Reset(person)}}ij}// 收集结果result:make([]int,0)fori:0;in;i{ifuf.IsConnected(i,0){resultappend(result,i)}}returnresult}复杂度分析时间复杂度O(m log m m α(n))排序O(m log m)并查集操作O(m α(n)) ≈ O(m)空间复杂度O(n)关键技巧总结时间分组同一时间的操作必须批量处理回退机制使用 Reset 撤销不合法的合并连通性判断只保留与源点连通的节点总结并查集是处理动态连通性问题的利器掌握以下要点✅基本操作Find路径压缩 Union按秩合并✅常见套路连通性判断、集合统计、时间维度处理✅优化技巧路径压缩 按秩合并时间复杂度接近 O(1)✅灵活应用根据题目需求添加 Reset、权重等扩展功能通过这道题目我们学会了如何处理带时间维度的并查集问题这是并查集高级应用的典型场景。