湖南 网站备案网站的pdf目录怎么做的

湖南 网站备案,网站的pdf目录怎么做的,设计学校,前端响应式网站2025-12-19#xff1a;包含 K 个连通分量需要的最小时间。用go语言#xff0c;给定一个含有 n 个顶点#xff08;编号 0 到 n-1#xff09;的无向图#xff0c;图中的每条边用三元组 edges[i] [ui, vi, timei] 表示#xff0c;含义是该无向边连接 ui 和 vi#xff0c;并…2025-12-19包含 K 个连通分量需要的最小时间。用go语言给定一个含有 n 个顶点编号 0 到 n-1的无向图图中的每条边用三元组 edges[i] [ui, vi, timei] 表示含义是该无向边连接 ui 和 vi并且会在时刻 timei 被删掉。再给定一个整数 k。初始时图可以是连通的也可以是不连通的。现在希望找到一个最早的时间 t使得把所有 time t 的边都移除后图被分成的连通子图数量至少达到 k。连通子图指的是任意两个顶点间有路径相通且该子图与外部没有边相连。返回满足上述条件的最小 t。1 n 100000。0 edges.length 100000。edges[i] [ui, vi, timei]。0 ui, vi n。ui ! vi。1 timei 1000000000。1 k n。不存在重复的边。输入 n 2, edges [[0,1,3]], k 2。输出 3。解释最初图中有一个连通分量 {0, 1}。在 time 1 或 2 时图保持不变。在 time 3 时边 [0, 1] 被移除图中形成 k 2 个连通分量{0} 和 {1}。因此答案是 3。题目来自力扣3608。 详细步骤说明1. 边按时间降序排序首先对所有边按照time字段进行降序排序。这样做的目的是让我们能够从最晚被删除的边开始处理逐步向图中添加边相当于逆向模拟边的删除过程。排序后时间最大的边排在前面时间最小的边排在后面。2. 初始化并查集创建一个包含n个顶点的并查集数据结构。初始状态下每个顶点都是一个独立的连通分量连通分量数量cc为n并查集包含两个主要操作find(x): 查找顶点x所在集合的代表元同时进行路径压缩优化merge(from, to): 合并两个顶点所在的集合3. 逆向添加边处理按排序后的顺序遍历每条边从时间最大的边开始处理每条边e [ui, vi, timei]的步骤检查顶点ui和vi当前是否属于同一连通分量如果不在同一分量则合并这两个分量连通分量数量减1合并后检查当前连通分量数量是否小于k如果是说明上一条处理的边也就是当前边的前一条边的时间就是我们要找的t因为继续添加边会导致连通分量进一步减少而我们需要的是连通分量至少为k的最小时间4. 确定结果当发现添加某条边后连通分量数量变得小于k时返回当前边的时间值作为结果这是因为移除所有time 当前边时间的边后连通分量数量刚好达到k如果遍历完所有边后连通分量数量仍然大于等于k则返回0表示不需要移除任何边就能满足条件。⚙️ 算法复杂度分析 时间复杂度O(m α(m, n))边排序O(m log m)其中m是边的数量并查集操作每个find和merge操作的时间复杂度接近常数为O(α(n))其中α是反阿克曼函数总体排序占主导地位但并查集操作也非常高效 空间复杂度O(n m)并查集存储O(n)用于存储每个顶点的父节点信息边排序O(m)用于存储排序后的边列表总体线性空间复杂度适合处理大规模数据 核心思路总结这个算法的关键在于逆向思考不是正向模拟边的移除而是从完全断开的状态开始逐步连接顶点。通过并查集高效维护连通分量结合排序确保按时间顺序处理最终在连通分量数量降至k以下时确定临界时间点。Go完整代码如下packagemainimport(fmtslices)typeunionFindstruct{fa[]int// 代表元ccint// 连通块个数}funcnewUnionFind(nint)unionFind{fa:make([]int,n)// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己fori:rangefa{fa[i]i}returnunionFind{fa,n}}// 返回 x 所在集合的代表元// 同时做路径压缩也就是把 x 所在集合中的所有元素的 fa 都改成代表元func(u unionFind)find(xint)int{// 如果 fa[x] x则表示 x 是代表元ifu.fa[x]!x{u.fa[x]u.find(u.fa[x])// fa 改成代表元}returnu.fa[x]}// 把 from 所在集合合并到 to 所在集合中func(u*unionFind)merge(from,toint){x,y:u.find(from),u.find(to)ifxy{// from 和 to 在同一个集合不做合并return}u.fa[x]y// 合并集合。修改后就可以认为 from 和 to 在同一个集合了u.cc--// 成功合并连通块个数减一}funcminTime(nint,edges[][]int,kint)int{slices.SortFunc(edges,func(a,b[]int)int{returnb[2]-a[2]})u:newUnionFind(n)for_,e:rangeedges{u.merge(e[0],e[1])ifu.cck{// 这条边不能留即移除所有 time e[2] 的边returne[2]}}return0// 无需移除任何边}funcmain(){n:2edges:[][]int{{0,1,3}}k:2result:minTime(n,edges,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListclassUnionFind:def__init__(self,n:int):self.falist(range(n))# 代表元self.ccn# 连通块个数deffind(self,x:int)-int:返回 x 所在集合的代表元同时做路径压缩ifself.fa[x]!x:self.fa[x]self.find(self.fa[x])# fa 改成代表元returnself.fa[x]defmerge(self,from_:int,to:int)-None:把 from_ 所在集合合并到 to 所在集合中x,yself.find(from_),self.find(to)ifxy:# from_ 和 to 在同一个集合不做合并returnself.fa[x]y# 合并集合self.cc-1# 成功合并连通块个数减一defminTime(n:int,edges:List[List[int]],k:int)-int:# 按 time 从大到小排序edges.sort(keylambdax:x[2],reverseTrue)uUnionFind(n)foru_,v,timeinedges:u.merge(u_,v)ifu.cck:# 这条边不能留即移除所有 time time 的边returntimereturn0# 无需移除任何边if__name____main__:n2edges[[0,1,3]]k2resultminTime(n,edges,k)print(result)C完整代码如下#includeiostream#includevector#includealgorithmusingnamespacestd;classUnionFind{private:vectorintfa;// 代表元intcc;// 连通块个数public:UnionFind(intn):fa(n),cc(n){// 一开始有 n 个集合 {0}, {1}, ..., {n-1}// 集合 i 的代表元是自己for(inti0;in;i){fa[i]i;}}// 返回 x 所在集合的代表元// 同时做路径压缩也就是把 x 所在集合中的所有元素的 fa 都改成代表元intfind(intx){// 如果 fa[x] x则表示 x 是代表元if(fa[x]!x){fa[x]find(fa[x]);// fa 改成代表元}returnfa[x];}// 把 from 所在集合合并到 to 所在集合中voidmerge(intfrom,intto){intxfind(from);intyfind(to);if(xy){// from 和 to 在同一个集合不做合并return;}fa[x]y;// 合并集合。修改后就可以认为 from 和 to 在同一个集合了cc--;// 成功合并连通块个数减一}intgetCC()const{returncc;}};intminTime(intn,vectorvectorintedges,intk){// 按 time 从大到小排序sort(edges.begin(),edges.end(),[](constvectorinta,constvectorintb){returna[2]b[2];});UnionFindu(n);for(constautoe:edges){u.merge(e[0],e[1]);if(u.getCC()k){// 这条边不能留即移除所有 time e[2] 的边returne[2];}}return0;// 无需移除任何边}intmain(){intn2;vectorvectorintedges{{0,1,3}};intk2;intresultminTime(n,edges,k);coutresultendl;return0;}