自力AC。
とりあえず、答えの個数を聞くため、S={1, 2,..., n}、とし、全ての始点に対して質問しなくてはいけなそう。それらをメモしAとしておく。
その後、xが始点なら、A[x]=A[y]+1となっていて、かつx→yに辺があるものを探していけば良い。
のだが、このクエリ回数がn以下になることが分からず考え込んでしまった。
ちゃんと考えると、A[i]=kとなるiを一つ見つけたらk-1を探し始めれば良いため、このパート全体でn回質問すれば済む。
なので、全体でのクエリ回数は2*n回に抑えられている。
0 件のコメント:
コメントを投稿