競プロ典型90問 083 Colorful Graph（★6）

この解説で想定する状況

結びつきが多い/少ないでわける。多い方が大。少ないほうが小。
左から小大小大小。
結びつきの線は図に書かれている他にもあると考えてください。

一番右は小で、小と大の2つにつながっている。
右から2番目は大で、小と大の2つにつながっている。

記録をする配列

記録をする配列は2つ。上のものは大でのみ使う。

模範回答(083–02a.cpp)の図解

上の配列の名前が update_large
下の配列の名前が update

小に書くとき

update の自分の場所に書く
update のつながっているところに書く

大に書くとき

小を読むとき

update の自分を読む
udate_large のつながっている大を読む

大を読むとき

update の自分を読む(つながっている小から書き込まれている)
update_large の自分を読む
update_large のつながっている大を読む