欢迎光临
我们一直在努力

D006 【模板】并查集

推荐阅读地址为:D006 【模板】并查集

并查集是非常灵活和高效的数据结构,常见应用是维护无向图的连通分量个数、大小,最小生成树的 Kruskal 算法和最近公共祖先等。

并查集维护了若干个不相交的集合,每个集合通过一棵树来组织,根节点为该集合的代表。

三个基本操作:

  • init(n) :初始化含有

    n

    n

    n 个集合的并查集,每个集合的代表为自身。

  • find(x) :寻找元素

    x

    x

    x 所在集合的代表。

  • union(x, y) :将元素

    x

    ,

    y

    x,y

    x,y 所在的集合合并,如果已经是处于同一集合的话就不合并。

  • 一个简单的并查集示例,可以先看图理解,再理解代码结构。

    并查集初始化、合并即查找图例

    图示的一个关键理解是:当 fa[x] == x 时,说明 x 是根节点。

    初始化代码

    def __init__(self, n):
    self.fa = list(range(n + 1))

    find 函数查找到元素所在集合的根,并且在查找过程中进行路径压缩(Path Compression)。

    路径压缩目的是把树的高度压低,使得长链可以变成扁平的放射状,从而大大降低时间复杂度。

    递归写法(直观、适合带权并查集写法)

    def find(self, x):
    if self.fa[x] == x:
    return x

    root = self.find(self.fa[x])
    self.fa[x] = root
    return root

    非递归写法(Python 推荐,避免栈溢出)

    这里采用路径减半策略,效率高且代码简洁。

    def find(self, x):
    while self.fa[x] != x:

    self.fa[x] = self.fa[self.fa[x]]
    x = self.fa[x]
    return x

    在查找时当自身不是根时往上跳,跳到根节点,然后再返回的过程中改变途径节点的父节点,统一改成根。

    合并的话先使用 find 函数找到对应的根,再链接即可。

    def union(self, x, y):
    rx = self.find(x)
    ry = self.find(y)
    if rx != ry:
    self.fa[rx] = ry # 将 rx -> ry

    这里也可以使用一个简单的启发式策略——按秩合并。维护一个 size 数组把小集合挂到大集合里去。

    def union(self, x, y):
    rx = self.find(x)
    ry = self.find(y)
    if rx != ry:
    self.fa[rx] = ry # 将 rx -> ry
    if size[rx] > size[ry]:
    rx, ry = ry, rx
    self.fa[rx] = ry
    size[ry] += size[rx]

    具体模板为

    class DSU:
    def __init__(self, n):
    self.fa = list(range(n + 1))

    def find(self, x):
    while self.fa[x] != x:
    self.fa[x] = self.fa[self.fa[x]]
    x = self.fa[x]
    return x

    def union(self, x, y):
    rx = self.find(x)
    ry = self.find(y)
    if rx != ry:
    self.fa[rx] = ry

    def is_same(self, x, y):
    rx = self.find(x)
    ry = self.find(y)
    return rx == ry

    赞(0)
    未经允许不得转载:171主机测评 » D006 【模板】并查集
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址