看题解区的 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) 的,logn 是并查集的 log。请问这如何证明?
我觉得这个 log 是启发式合并若干长度相近的环的 log,再乘上并查集的复杂度,不知道大家怎么看?