某岛

… : "…アッカリ~ン . .. . " .. .
July 30, 2020

BZOJ 4025. 二分图

BZOJ 4025. 二分图

DarkBZOJ 传送门
https://www.cnblogs.com/ZeonfaiHo/p/7502056.html

题意

给定一个 n 个点, m 条边的无向图, 每条边在一定时间范围内存在. 要你判断每个时间点这张图是否为二分图。(n ≤ 1e5,m≤2e5)

题解

我们可以用 Link-Cut Tree 离线的维护图的连通性,方法是我们把图当成树来处理,维护出路径上最脆弱的边(也就是最早消失的边)即可,当新插入的边连接的两个点已经处在一个连通分量时,如果新的边更加健康,我们就去替换掉那条边,关于 Link-Cut Ttre 维护路径最值的操作,参考 HDU 4010

(这好像其实也就是 Link-Cut Tree 最正经的用途之,优化网络流!)

回到这个题,我们只需要再维护一下路径的 size,判断一下是否有奇数个点(或者偶数条边)即可,由于现在考察的对象既有边又有点,还有换根操作,着实容易写错,干脆的把原图中的边也放进 Link-Cut Tree 里去维护。

代码