Official
D - Neighbors Editorial by kyopro_friends
どの人も高々 \(2\) 人としか隣り合うことはできません。したがって、条件の中に \(3\) 回以上登場する人がいた場合、答えは No
です。この判定は \(O(N+M)\) で容易に行えます。
また、\((A_i,B_i)=(1,2),(1,3),(2,3)\) などのように、ループする条件がある場合も No
です。この判定はUnion-FindやBFS, DFSなどを用いることで \(O(N+M)\) などで行なえます。
逆に、以上の \(2\) 条件に抵触しない場合、(実際に並べて確かめることなく!)答えは Yes
となるため、この問題が解けました。
posted:
last update: