C - 森ですか?

Quiz

https://atcoder.jp/contests/utpc2012/tasks/utpc2012_03

Submission

https://atcoder.jp/contests/utpc2012/submissions/5717188

解法

  • N=5000など大きい時、辺の本数 N*(N-1)/2 = 125万ほど
  • Q=100000で辺を取っても木になりえないので全てN
  • より厳密には、辺の本数が N-1 以下でないと森になりえない
    • N*(N-1)/2 - Q <= N-1
    • じゃないと森になりえない
  • この条件を抜けた時、Nは小さい値になっている
    • 上記式をイコールで解くと、N2=Qに近くなり、最大でもN=400程度
  • 辺の本数はN-1程度
    • 閉路判定の計算量はO(N)
  • クエリごとに閉路判定したとしても、100000 * 400 = 4 * 107
  • よって解けました

閉路判定

  • Union Findを使った

ポイント

  • Nが大きいときと小さい時で遷移を変える

Note

f:id:peroon:20190601080556j:plain