本题还涉及到遍历并查集的操作,核心是p[x] == x
for x in p: # 遍历并查集
if p[x] == x: # 如果该节点的父节点是它自己,那就说明该节点是集合的代表元素
pass
- 在读入时将边的信息存到edges列表中,以便之后遍历边进行集合的合并操作
- 将一个集合中的信息都存到根节点中,因为根节点是集合的代表元素,遍历并查集时也好操作一点。开3个字典,
nums
,M_estate
,area
,其中nums
表示该集合中点的数量,M_estate
是其该集合所有成员房产数量之和,area
是该集合所有成员的房产的总面积之和 - 由于输出时题干要求
ID
是家庭成员中编号最小的成员编号,所以合并集合时把编号较大的集合放到编号较小的集合下面去,这样可以保证每个集合的根节点(即这个集合的代表元素)编号是最小的
本题完整代码:
from collections import defaultdict
n = int(input())
# p用于并查集的父节点指向
# nums表示该集合中点的数量
# M_estate是其该集合所有成员房产数量之和
# area是该集合所有成员的房产的总面积之和
p = {}
nums = defaultdict(lambda: 1)
M_estate = defaultdict(lambda: 0)
area = defaultdict(lambda: 0)
# 初始化边列表,用于存储图中的边
edges = []
# 读取每个节点的信息
for _ in range(n):
s = input().split()
id = s[0]
p[id] = id # 并查集初始化
M_estate[id] = int(s[-2])
area[id] = int(s[-1])
for i in range(1, 3):
if s[i] != "-1":
p[s[i]] = s[i] # 并查集初始化
edges.append([s[0], s[i]])
k = int(s[3])
for i in range(4, 4 + k):
p[s[i]] = s[i] # 并查集初始化
edges.append([s[0], s[i]])
# 定义并查集的find函数,用于查找节点的根节点
def find(x):
if p[x] != x:
p[x] = find(p[x]) # 路径压缩,直接连接到根节点
return p[x]
# 遍历边列表,合并集合
for x, y in edges:
pa = find(x)
pb = find(y)
if pa != pb: # 如果两个节点不在同一个集合中
if pa > pb: # 确保pa是较小的编号,方便后续处理
pa, pb = pb, pa
# 合并集合,更新集合大小、特定值的总和等信息
nums[pa] += nums[pb]
M_estate[pa] += M_estate[pb]
area[pa] += area[pb]
p[pb] = pa # 将pb的父节点指向pa
# 初始化家族列表,用于存储每个集合的信息
family = []
for x in p:
if p[x] == x: # 如果x是某个集合的根节点
avg_sets = M_estate[x] / nums[x]
avg_area = area[x] / nums[x]
# 将集合信息添加到家族列表中
family.append([x, nums[x], avg_sets, avg_area])
# 按人均房产面积降序,如果平均值相同,则按节点编号升序排序
family.sort(key=lambda x: (-x[3], x[0]))
# 输出家族数量
print(len(family))
# 输出每个家族的信息,包括家庭成员中编号最小的成员编号、家庭成员数、人均房产套数和人均房产面积
for i, j, k, x in family:
print("{} {} {:.3f} {:.3f}".format(i, j, k, x))