🪷
競プロ典型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
のつながっている大を読む
Discussion