Quiz
- https://codeforces.com/contest/1176/problem/E
- 高々N/2個の頂点で点被覆せよ
AC
- https://codeforces.com/contest/1176/submission/55399046
- bfsで黒と白(0, 1)に塗っている
解法
- グラフを2色に塗る（例えば白と黒とする）
- 現在見ているノードを白で塗ったなら、隣はできるだけ黒で塗るようにする
- 塗り終わった時、数の少ない色の方を答えとして出力
参考
(→)
— satanic@競プロ🔥 (@satanic0258) 2019年6月9日
D:最大値Mを見て,Mが素数ならM<p_Mよりあるkが存在してp_k=Mなのでkをaに入れkとMをbから消す.Mが合成数ならMの最小素因数qとしてM>M/qよりM/qをaに入れM,M/qをbから消す.これをbが空になるまでやる
E:グラフを2色で彩色(同色が隣り合っても気にしない)する,少ない方の色の頂点たちが答え
(→)
私の誤解法
- （白で最小点被覆を貪欲にやろうとして・・・↓）
- 次数多い点から取り出して、まだ塗られていないなら白で塗り、その隣は塗られていなければ黒で塗る
- 白を答えとして出力する
- ダメな例
別解
- dfsで2色に塗っても通った
- https://codeforces.com/contest/1176/submission/105019182
- ただ、グラフが木じゃない時のdfsは塗り順をイメージしづらいので避けた方がいいかも
