故障域时标同步
P5941. 故障域时标同步
场次:2026年10月21日-非AI方向 · 来源:CodeFun2000 P5941
题目描述
整套装置里安放了 块转发芯片,编号从 编到 。报文进出这些芯片时,时间戳必须对齐。对齐靠芯片互相传递时标信息完成,这一过程叫做时标同步。
对齐遵守下列约定。
每块芯片把自身的时标权重 写进时标信息,再沿着尚未断开的链路,把信息交给所有还能走到的芯片。
能够彼此走到的芯片组成一个时标域。域内挑出权重 最高的芯片当作时标源,其他芯片改用它的时标。若好几块芯片的权重同为最高,就改挑其中编号最小的那一块。走不到任何其他芯片的,自己单独组成一个时标域。
眼下大量链路已经损坏,不少芯片再也走不到对方,装置会裂成好几个时标域。排查并修复时,要查出指定芯片正跟随哪一个时标源,也就是它所在域里被挑中的那块芯片的编号。
输入格式
评测机经由标准输入送入全部数据。
第一行是两个整数 和 。 为芯片块数, 为仍然保留的链路条数。
第二行是 个整数,按编号 到 的顺序,给出每块芯片的时标权重 。
其后 行,每行两个整数 和 ,表示编号 与编号 之间有一条双向链路。同一对端点可以写多次,芯片也可以连到自己,这些写法都不增加新的可达关系。
下一行是一个整数 ,表示询问次数。
最后一行是 个整数 ,为被点名芯片的编号。点名从左到右各回答一次。
输出格式
只打印一行。这一行含有 个整数,彼此以单个空格相隔,开头和结尾都不留空格。从左往右,第 个整数就是第 次询问所对应的时标源编号。
数据范围
示例
示例 1
输入:
5 3
4 1 4 7 2
0 2
2 1
3 4
4
2 4 1 0输出:
0 3 0 0说明:
三条链路把五块芯片分成两块:编号 、、 互相走到,编号 、 互相走到。
前一块的权重是 、、。最高权重为 ,编号 与编号 并列,取更小的编号 。
后一块的权重是 、,被挑中的是编号 。
四次点名依次是 、、、,答案依次是 、、、。
示例 2
输入:
7 4
2 6 8 5 9 9 1
0 1
1 3
3 0
4 5
6
0 3 1 5 2 6输出:
1 1 1 4 2 6说明:
四条链路实际分成四块,重复的 — 不改变分块。
编号 、、 在同一块,权重为 、、。最大权重在编号 。编号 更靠前,但权重更低,不能当基准。
编号 单独成块,基准是 。编号 同样单独成块,基准是 。
编号 与编号 的权重都是 ,取更小的编号 。
六次点名依次是 、、、、、,答案依次是 、、、、、。
分块示意(括号内为编号):
(0)---(1)---(3)
(2)
(4)---(5)
(6)解题思路
一个询问的答案是什么
题面对时标源的定义只有两条,读准这两条,整题就没有别的花样:
- 范围:只看「能彼此走到」的那一批芯片,也就是图里的一个连通块。链路是双向的,所以「 能走到 」是一个等价关系——自反、对称、传递,于是它把 块芯片切成若干互不相交的块。
- 挑选:块内权重 最大者胜;权重并列时编号最小者胜。
因此每个询问都是同一个动作:先找到点名芯片所在的块,再读出这块预存的时标源编号。「找到块」和「读出时标源」这两步必须拆开做,因为 最大 ,每个询问都重新扫一遍所在块会退化成 。
为什么用并查集,而不是每个询问做一次 BFS
把芯片切成连通块,并查集是最短的一把刀:读到一条链路就把两端 union 起来,最后一次遍历所有芯片,按下标升序把每个块的时标源定下来,之后每个询问只做一次 find 加一次查表,。
数据范围也给了同样的信号:、、。三条都是「预处理一次、查询多次」的形状——如果只有一次询问,BFS 和并查集都行;有 次询问时,答案必须能 取出来。
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root: # 路径压缩
parent[x], x = root, parent[x]
return root
for _ in range(b):
u = int(data[pos]); v = int(data[pos + 1]); pos += 2
ru, rv = find(u), find(v)
if ru != rv:
if size[ru] < size[rv]: # 按大小合并,树高保持在 log 级
ru, rv = rv, ru
parent[rv] = ru
size[ru] += size[rv]题面特意交代了「同一对端点可以写多次,芯片也可以连到自己」。这两种写法在 union 里都落到同一条路径上:find(u) == find(v) 时直接跳过,不会把块切错,也不会多算。
时标源:按编号升序扫一遍就够
关键只有一句:编号升序 + 只在严格更大时换人。这样一来,同一块里权重更大的芯片一定后来居上,而权重相同的芯片谁也不会顶掉谁,先到的小编号自然留在 leader 上——并列取小这条规则不需要单独写一行比较。
best_w[root] 记的是「这块目前见到的最大权重」,leader[root] 记的是「拿到这个最大权重的那块芯片的编号」,两者必须按块(也就是按根)存,而不是按芯片存。
leader = list(range(a))
best_w = weight[:]
for x in range(a): # 编号升序
root = find(x)
if weight[x] > best_w[root]: # 严格更大才换
best_w[root] = weight[x]
leader[root] = x
elif weight[x] == best_w[root] and x < leader[root]:
leader[root] = x编号本身就是升序遍历的,所以只留 > 一条判断也已经正确;elif 那一行是冗余保险——即便换成别的遍历顺序,leader 仍会落在「同权重里编号最小」的那块芯片上。两行合起来的含义就是「取 (权重最大, 编号最小)」,读的时候不必依赖遍历顺序。
回答询问
out = [str(leader[find(int(g))]) for g in data[pos:pos + t]]
print(" ".join(out))每个询问只做一次 find(回答时也可以先不压缩,正确性不受影响;压缩只是让后续询问更快)。
完整代码实现
import sys
sys.setrecursionlimit(300000)
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
pos = 0
a = int(data[pos]); b = int(data[pos + 1]); pos += 2
weight = [int(x) for x in data[pos:pos + a]]; pos += a
parent = list(range(a))
size = [1] * a
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root: # 路径压缩
parent[x], x = root, parent[x]
return root
for _ in range(b):
u = int(data[pos]); v = int(data[pos + 1]); pos += 2
ru, rv = find(u), find(v)
if ru != rv: # 自环与重复链路在这里被吞掉
if size[ru] < size[rv]:
ru, rv = rv, ru
parent[rv] = ru
size[ru] += size[rv]
# 编号升序遍历,只在权重严格更大时换人 → 并列时留下更小的编号
leader = list(range(a))
best_w = weight[:]
for x in range(a):
root = find(x)
if weight[x] > best_w[root]:
best_w[root] = weight[x]
leader[root] = x
elif weight[x] == best_w[root] and x < leader[root]:
leader[root] = x
t = int(data[pos]); pos += 1
out = [str(leader[find(int(g))]) for g in data[pos:pos + t]]
sys.stdout.write(" ".join(out) + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1:三块芯片的并查集长什么样
输入是 、,权重按编号 依次是 ,链路是 、、。
第一步,建块。 三条链路依次 union:
| 读到的链路 | 操作 | 结果 |
|---|---|---|
| 两块合并 | ||
| 并入 | ||
| 两块合并 |
得到两个块: 与 。
第二步,按编号升序扫时标源。
| 芯片 | 权重 | 所在块 | 扫描后的 best_w / leader |
|---|---|---|---|
| / | |||
| / (权重更小,不动) | |||
| / (权重相等不顶掉,编号也更大) | |||
| / | |||
| / (权重更小,不动) |
于是两个块的时标源是 和 。
第三步,回答四次点名。
| 点名 | 所在块 | 时标源 |
|---|---|---|
输出 0 3 0 0,与题面一致。
示例 2:重复链路与孤立芯片
四条链路是 、、、。前三条首尾相接,union 之后 已经在同一块,所以第三条()进来时 find(3) == find(0),直接跳过;它既不改变分块,也不会把权重表弄乱。
按编号升序扫时标源:芯片 权重 起头,芯片 权重 顶掉它成为 号块的暂定源,芯片 权重 小于 不动;芯片 与 各自成块,源就是自己; 里权重同为 ,先到的 留下。
这正好覆盖了题面的两条边界:权重相同取小编号( 与 )与孤立芯片自成一块(、)。六次点名 依次得到 。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 每个询问现做一次遍历,扫出所在块与时标源 | 时是 量级,必超时 | ||
| 并查集预处理 + 每个询问 查表(最优) | 是反阿克曼函数,实际可视为常数 |
并查集部分: 条链路各做两次 find,按大小合并让树高保持在 ,路径压缩后再降一档;时标源那一遍是 ;询问 次各一次 find。空间上 parent、size、weight、leader、best_w 都是长度 的数组,链路的边根本不需要存——这也是并查集比建邻接表再做 BFS 省的地方。
易错点总结
1. 时标源用 >= 更新,并列时留下了大编号
把第二遍扫描写成 if weight[x] >= best_w[root]: 之后,同权重的后者会顶掉前者,leader 上留下的是最后读到的那个编号。示例 1 的 里权重 有 和 两块芯片,此时示例 1 的输出会变成 2 3 2 2,与题面的 0 3 0 0 不同。改成严格 >(再配一条 x < leader[root] 的 elif)才是题面要的「并列取小编号」。
2. 用递归 DFS 代替并查集,长链上直接爆栈
若改成「对每块未访问的芯片开一次 dfs,在递归里顺便挑出块内最大权重」, 的一条链()就会递归 层。Python 默认递归上限约 ,运行到一半抛 RecursionError,而输出是最后统一打印的,页面上表现为一行输出都没有——看起来像读入失败,实际是栈溢出。