做健康食品的网站,金融行业做网站需要什么,百度有刷排名软件,网站建设服务怎么样文章目录 总述合并过程查找过程算法实战实战1 总述 并查集#xff08;Disjoint-set Union#xff0c;简称并查集#xff09;是一种用来管理元素分组情况的数据结构。它主要用于解决集合的合并与查询问题#xff0c;通常涉及到以下两种操作#xff1a; 合并#xff08;Uni… 文章目录 总述合并过程查找过程算法实战实战1 总述 并查集Disjoint-set Union简称并查集是一种用来管理元素分组情况的数据结构。它主要用于解决集合的合并与查询问题通常涉及到以下两种操作 合并Union 将两个集合合并成一个集合。查询Find 查找某个元素所属的集合。 并查集通常应用于解决连接问题如判断无向图中的连通分量、网络连接状态的判断、社交网络中的好友关系等。在算法竞赛和数据结构课程中也经常会涉及到并查集的应用场景比如 Kruskal 算法中的边权值排序以及求解最小生成树等。 合并过程 合并的过程就是先找到两个元素的根若根不相同则将其中的一个根的父节点改成另一个根节点 s [i for i in range(N1)] # 列表s[i] 表示i 节点的父节点开始的时候全部指向自己
def union(x,y):r1 find(x)r2 find(y)if r1 ! r2:s[r1] s[r2]
查找过程 对于查找的过程就是一直找 def find(x): # 返回 x 的根节点if x ! s[x]:s[x] find(s[x])return s[x]
算法实战
实战1 from collections import defaultdictn int(input())
p [i for i in range(n 1)] # p[i] 表示 节点 i 的父节点
tree defaultdict(list) # 输入键当键不存在就生成键列表
used [0] * (n 1) # 用来记录是否访问过
ans [0] * n # 用来反复记录路径def find(x): # 并查集的查找函数返回x 节点的根if x ! p[x]:p[x] find(p[x])return p[x]def dfs(pos, idx):ans[idx] posif pos end:res sorted(ans[:idx 1]) # 排序print( .join(map(str, res))) # 输出间隔空格输出 returnfor d in tree[pos]: # 逐一访问节点的邻接节点if not used[d]: # 由于是无向图并且加上深度搜索所以要记录一个节点是否已经访问过used[d] 1dfs(d, idx 1)for _ in range(n):u, v map(int, input().split()) tu, tv find(u), find(v) if tu tv:start, end u, v break # 所以是不必加载全部的边的关系的因为当两个输入的节点的根相同的时候就说明已经包含环了else:p[tv] tutree[u].append(v)tree[v].append(u) # 无向图used[start] 1
dfs(start, 0) 代码分析 不能直接暴力地去深度搜索会超时用并查集来判断两个节点是否位于不同的连通分支并查集并不是死板地运用全部的合并和查找函数深度搜索只是一种工具并不是死板地运用全部的框架
