社区讨论

关于时间复杂度的问题

2275307894a
P6113 【模板】一般图最大匹配参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo2krzsq
此快照首次捕获于
2023/10/23 15:27
2 年前
此快照最后确认于
2023/10/23 15:27
2 年前
查看原帖
看题解区的 blossom 函数都差不多是这么写的：
CPP
inline void blossom(register int x,register int y,register int w){
	while(find(x)!=w){
		pre[x]=y,y=match[x];
		if(vst[y]==2)vst[y]=1,q.push(y);
		if(find(x)==x)p[x]=w;
		if(find(y)==y)p[y]=w;
		x=pre[y];
	} 
}
其中 x=pre[y] 这一句没有通过并查集加速，复杂度也就不能简单通过均摊理解。但是大部分博客直接说这是 O(m)O(m) 的，log⁡n\log n 是并查集的 log⁡\log。请问这如何证明？
我觉得这个 log⁡\log 是启发式合并若干长度相近的环的 log⁡\log，再乘上并查集的复杂度，不知道大家怎么看？

回复

共 0 条回复，欢迎继续交流。

正在加载回复...