- Quiz
- D The Number of Imposters
- https://codeforces.com/contest/1594/problem/D
- 感想
- 有向グラフの問題に見えるが、よく考えると無向グラフ
- imposterと言っているなら、頂点x, yは違う色
- crewmateと言っているなら、頂点x, yは同じ色★
- ★について、色はまだ不明だけど同じ色であることは確定しているときに使えるのがfake node。x---fake_node---yのように繋げる
- editorialに書いていて、初めて知った
- 後は（連結成分ごとに）2部グラフであることを確認して、多い色の方をimposterとして数えればいい
- editorial
- 元ネタ：among us
