競技プログラミング用 知識集積所
ABC451F - Make Bipartite 3
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
とりあえず二部グラフ※にできるかどうかの判定は、頂点倍加※とUnionFind木※を用いた方法で可能。
すなわち、頂点数2NのUnionFind木※を用意し、頂点UとVが辺で繋がれている場合「Uを白」と「Vを黒」を、また「Uを黒」と「Vを白」を連結する。
これらを連結した後で「Uを白」と「Uを黒」が連結されてしまっていたら、二部グラフ化は不可能。
ここまでは典型問題。
すなわち、頂点数2NのUnionFind木※を用意し、頂点UとVが辺で繋がれている場合「Uを白」と「Vを黒」を、また「Uを黒」と「Vを白」を連結する。
これらを連結した後で「Uを白」と「Uを黒」が連結されてしまっていたら、二部グラフ化は不可能。
ここまでは典型問題。
問題は、最小の黒頂点の個数をどう求めるか。
これは、UnionFind木※の各連結成分上の黒頂点数を管理し、白黒入れ替えただけの成分ペアのうち黒の個数が小さい方だけを採用すると考えればよい。
自作のUnionFind木※を改造するか、ACLに頼る場合はUとVのleaderを見て外部のvectorで頑張って記録する。
愚直に毎回足すとTLEするので、差分更新※で処理すること。
これは、UnionFind木※の各連結成分上の黒頂点数を管理し、白黒入れ替えただけの成分ペアのうち黒の個数が小さい方だけを採用すると考えればよい。
自作のUnionFind木※を改造するか、ACLに頼る場合はUとVのleaderを見て外部のvectorで頑張って記録する。
愚直に毎回足すとTLEするので、差分更新※で処理すること。
