[問題案] Planarity Testing

[hly1204]

(任意) 問題ID: planarity_testing 問題名: Planarity Testing

(任意) 想定アルゴリズム: Hopcorft-Tarjan Algorithm or PQ-trees or PC-trees (任意) 参考資料: https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/planarity.pdf

問題概要

Testing the planarity of a graph

入力

a graph with n vertices and m undirected edges

n m
f_0 t_0
...
f_{m-1} t_{m-1}

出力

True or False

制約

n, m <= 10^{6}

[yosupo06]

Look good to me (sorry for slow reply).

I recommends to:

• graph don't have to be connected
• graph doesn't contain multiple edges / self-loop
• print (Yes / No) (just my prefer)