競プロ典型90問 083
Colorful Graph（★6）
Published in
Jun 29, 2024
問題
解説で想定する状況
結びつきが多い/少ないでわける。多い方が大。少ないほうが小。
左から小大小大小。
線は図に書かれている他にもあると考えてください。
一番左は小で、小と大の2つにつながっている。
右から2番目は大で、小と大の2つにつながっている。
記録をする配列は2つ。上のものは大でのみ使う。
模範回答(083–02a.cpp)の図解
上の配列の名前が update_large
下の配列の名前が update
小に書くとき
update の自分の場所に書く
update のつながっているところに書く
大に書くとき
update_large の自分の場所に書く
小を読むとき
update の自分を読む
udate_large のつながっている大を読む
大を読むとき
update の自分を読む(つながっている小から書き込まれている)
update_large の自分を読む
update_large のつながっている大を読む
