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