带权并查集

来自4.12蓝桥杯python B组

原题复现：



题目描述

为了提升用户粘性，平台产品经理提出了全新的”圈层互动”功能。系统中共有 NN 个用户结点，初始时，每位用户的”活跃度”均为 00，且彼此之间处于陌生人状态，没有任何社交关联。

随着产品功能的上线，后台日志将按顺序记录 QQ 条用户行为指令。这些指令如下：

  1. 建立好友：用户 XX 与用户 YY 相互关注，双方所在的社交圈正式连通。若两者已处于同一社交圈，则忽略此操作。
  2. 发布个人动态：用户 XX 发布了一条个人动态，其个人活跃度提升 AA 个单位。
  3. 圈层热议：用户 XX 发起了一个热门话题，该话题产生极强的辐射效应，使得所有与 XX 处于同一社交圈（即通过好友关系可直接或间接连通）的用户，其活跃度同步追加 AA 个单位。
  4. 数据查询：运营团队请求获取用户 XX 当前的活跃度数，用于分析用户质量。

随着用户量激增，高频的社交互动请求让服务器核心计算模块面临巨大压力。作为小蓝的协助者，请你接管日志处理单元，并按顺序输出所有的查询结果。

输入格式

第一行包含两个正整数 NN 和 QQ，分别代表平台用户总数与行为日志的总条数。

随后 QQ 行，每行描述一条具体的行为指令，格式遵循以下四种类型之一：

  • 11 XX YY: 执行"建立好友"，连通用户 XX 与 YY 的社交圈。
  • 22 XX AA: 执行"个人动态"，为用户 XX 的活跃度增加 AA。
  • 33 XX AA: 执行"圈层热议"，为 XX 所在社交圈内的所有用户活跃度增加 AA。
  • 44 XX: 执行"数据查询"，查询用户 XX 的当前活跃度。

输出格式

针对每一条”数据查询”指令，输出单独的一行整数，代表目标用户当前的活跃度数值。



解题报告

并查集的核心思路是以根节点作为元素集合的桥梁.

  • 初始化时,每个元素的根节点指向自身,即parent[x] = x.
  • 执行操作1”建立好友”时,先判断二者是否有共同根节点,若有,则可直接忽略,若无,则从二者中选取一个作为另一个的父节点,即parent[Y] = X.
  • 执行操作3”圈层热议”时,查找X的父节点并向上遍历,直至找到最终的初始根节点,初始根节点root满足parent[root] = root,然后将所有以root连通的元素加上附加值A.

另建数组user用来存储每个元素通过操作3积累的个人活跃度

简单并查集问题这就够了

然而这题是带权并查集😒

如果按简单的并查集操作几乎必然出现错误,当两个已存在的集合合并时,作为子节点的集合从操作3中积累的活跃度会全部丢失,因此需要另外建立权数组(表示节点相对其父节点的偏移量)weight来记录数据的权值

此题Q,N数据量达到2e5级别,Python实现时需要用sys.stdin.readline()快速读取

代码实现

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import sys
data = sys.stdin.read().split()
idx = 0
N = int(data[idx])
idx += 1
Q = int(data[idx])
idx += 1

parent = list(range(N))
user = [0] * N
extra = [0] * N
weight = [0] * N

def findRoot(x):
    if parent[x] != x:
        orig_p = parent[x]   
        parent[x] = findRoot(parent[x]) 
        weight[x] += weight[orig_p]
    return parent[x]

for _ in range(Q):
    op = int(data[idx])
    idx += 1

    if op == 1:
        X = int(data[idx]) - 1
        idx += 1
        Y = int(data[idx]) - 1
        idx += 1
        rx = findRoot(X)
        ry = findRoot(Y)
        if rx != ry:
            parent[ry] = rx
            weight[ry] = extra[ry] - extra[rx] #更新权值,因为rx集合下原有的活跃度不属于ry集合
        
    elif op == 2:
        X = int(data[idx]) - 1
        idx += 1
        A = int(data[idx])
        idx += 1
        user[X] += A

    elif op == 3:
        X = int(data[idx]) - 1
        idx += 1
        A = int(data[idx])
        idx += 1
        root = findRoot(X)
        extra[root] += A

    elif op == 4:
        X = int(data[idx]) - 1
        idx += 1
        root = findRoot(X)
        print(user[X] + extra[root] + weight[X])