关于时间复杂度的问题
查看原帖
关于时间复杂度的问题
181766
275307894a楼主2023/5/18 11:44

看题解区的 blossom 函数都差不多是这么写的:

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,再乘上并查集的复杂度,不知道大家怎么看?

2023/5/18 11:44
加载中...