并查集的应用

P1551 亲戚

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：$x$ 和 $y$ 是亲戚，$y$ 和 $z$ 是亲戚，那么 $x$ 和 $z$ 也是亲戚。如果 $x$，$y$ 是亲戚，那么 $x$ 的亲戚都是 $y$ 的亲戚，$y$ 的亲戚也都是 $x$ 的亲戚。

输入格式

第一行：三个整数 $n,m,p$，（$n,m,p \le 5000$），分别表示有 $n$ 个人，$m$ 个亲戚关系，询问 $p$ 对亲戚关系。

以下 $m$ 行：每行两个数 $M_i$，$M_j$，$1 \le M_i,~M_j\le n$，表示 $M_i$ 和 $M_j$ 具有亲戚关系。

接下来 $p$ 行：每行两个数 $P_i,P_j$，询问 $P_i$ 和 $P_j$ 是否具有亲戚关系。

输出格式

$p$ 行，每行一个 Yes 或 No。表示第 $i$ 个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例 #1

输入 #1

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

输出 #1

Yes
Yes
No

解决方案

对于森林的管理与查询，并查集是一种很高效的数据结构。

class Dsu:
    # 初始化
    def __init__(self, size):
        self.pa = list(range(size+1))

    # 查询_路径压缩
    def find(self, x):
        if self.pa[x] != x:
            self.pa[x] = self.find(self.pa[x])
        return self.pa[x]

    # 合并
    def union(self, x, y):
        self.pa[self.find(x)] = self.find(y)


def main():
    n, m, p = map(int, input().split())
    relatives = Dsu(n)

    # 有亲戚关系，进行合并操作
    for i in range(m):
        x, y = map(int, input().split())
        relatives.union(x, y)

    # 已经结束合并，进行查询操作
    for i in range(p):
        x, y = map(int, input().split())
        if relatives.find(x) == relatives.find(y):
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Bingo!

下面来看蓝桥杯真题，这是带权并查集的一种应用：

P11005 [蓝桥杯 2024 省 Python B] 缴纳过路费

题目描述

在繁华的商业王国中，$N$ 座城市被 $M$ 条商路巧妙地连接在一起，形成了一个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过
商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。

有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费总和，而是这条路线上最贵的那一次收费。这个标准简单而直接，让他能迅速评估出一条路线是否划算。

于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线成本介于他心中预设的两个数 $L$ 和 $R$ 之间。他相信，这样的路线既不会太廉价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。

作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。

输入格式

输入的第一行包含四个整数 $N, M, L, R$，表示有 $N$ 座城市和 $M$ 条双向通行的商路，以及小蓝心中预设的最高过路费的下限 $L$ 和上限 $R$。

接下来 $M$ 行，每行包含三个整数 $u, v,w$，表示城市 $u$ 和城市 $v$ 之间有一条双向通行的商路，过路费为 $w$。保证每对城市之间最多只有一条直接的商路。

输出格式

输出一行包含一个整数，表示满足条件的城市对数量。

输入输出样例 #1

输入 #1

5 5 1 2
1 2 2
1 3 5
1 4 1
2 4 5
2 5 4

输出 #1

3

说明/提示

对于 30% 的评测用例，$1 \le N \le 10^3,1 \le M \le \min(2 \times 10^3,\frac{N×(N−1)}{2}), 1 \le L \le R \le 10^5，1 \le u, v \le N, u \ne v,1 \le w \le 10^5$。

对于所有评测用例，$1 \le N \le 10^5,1 \le M \le \min(2 \times 10^5,\frac{N×(N−1)}{2}),1 \le L \le R \le 10^9,1 \le u, v \le N, u \ne v，1 \le w \le 10^9$。

样例解释

在样例中，满足条件的城市对有 $(1, 2),(1, 4),(2, 4)$。

解决方案

在这道题目当中我们可以将输入情况分为三种：

• 小于左边界值的
• 介于要求区间的
• 大于右边界值的
  不难发现，对于第三种情况我们是应当舍弃的，因为一旦途径这条边，一定没有符合要求的路径。
  
  其次是前两种情况，其中第二种情况是真正起作用的，是使得路径合法的，因此这种输入下，只要联通，城市之间都可以两两互相配对。但是对于第一种情况而言，直接相连的城市并不合法，需要删除。
  

class Dsu:
    def __init__(self, size):
        self.pa = list(range(size+1))
        self.size = [1] * (size+1)
        # 这里使用size数组来记录每个父节点下连接叶子节点的个数

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

    def union(self, x, y):
        xx, yy = self.find(x), self.find(y)
        if xx == yy:
            return
        self.pa[yy] = xx
        self.size[xx] += self.size[yy]

def c(x):
    return x * (x-1) // 2

def main():
    n, m, l, r = map(int, input().split())

    cities_1 = Dsu(n)
    cities_2 = Dsu(n)

    for i in range(m):
        u, v, w = map(int, input().split())
        if w <= r: cities_1.union(u, v)
        if w < l: cities_2.union(u, v)

    ans = 0
    for i in range(1, n+1):
        # 判断是不是父节点
        if cities_1.find(i) == i:
            ans += c(cities_1.size[i])
        if cities_2.find(i) == i:
            ans -= c(cities_2.size[i])

    print(ans)

if __name__ == "__main__":
    main()

Bingo!