Happy Coding

This blog is for my memorandum.

Happy Coding

This blog is for my memorandum

AtCoder Beginner Contest 030 D へんてこ辞書

問題文

ミカミくんは怪しい英単語帳を使っています。その単語帳には N 個の単語の意味が載っており、単語 i の説明には「単語 bi と同じ意味である」とだけ書いてあります。ここで、i 番目の単語を単語 i と呼ぶことにします。 ミカミくんはまだ一つの英単語も知らないので、単語 i の意味を調べようとしたとき、単語 bi の意味を調べようとします。ミカミくんは真面目なので、今までにすでに調べようとしたことのある単語でも同じように単語帳をひき続けます。 しかし、残念ながらこの単語帳では英単語の意味自体はどこにも書いていないため、意味を知ることはできません。 ある単語 i を調べようとして、単語帳を参照し、単語 bi を調べようとするまでを1ステップとします。

ミカミくんが単語 i を調べようとして、k ステップ経ったとき、ミカミくんはどの単語を調べようとしているでしょうか?

Note

グラフの閉路担ってる部分を見つけ出す問題。 kが大きすぎるせいで c++だとunsigned long long におさまらない。 javaのBigIntegerに逃げる。  なにげに初めてjava書いた。