NECプログラミングコンテスト2021 (AtCoder Beginner Contest 229) E - Graph Destruction (500)
連結を削除するのは大変だが、連結するのはUnionFindで簡単にできるので逆向きに考える
それぞれの辺について小さい方の頂点にその辺を紐付ける
それぞれの頂点$ iを逆向きに見て以下を行う
その地点での答えを答えの配列に代入
$ 連結成分数 - (i+1)
その頂点に紐付けられた辺について、それによって新たに連結する場合、連結して連結成分数を1減らす
$ \mathcal{O}(N+M\alpha(N))