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 里去維護。

代碼