競技プログラミング日記

主に AtCoder の記事です

クエリ逆算，クエリの差分
辺の削除より，辺の追加の方が簡単なので，そちらで考える．
一つ頂点を追加したときに，connected component がどの程度変化するのか，差分を求めることで高速にクエリを処理する．

大きい番号から頂点を追加していくので，辺を追加するときは，小さい番号から大きい番号への辺のみを追加する．

連結成分の個数の変化

頂点を追加したときに \(+1\) 個．
辺 \*1 uf.merge(a,i), c--;

}

ans.push_back(c);

}

reverse(all(ans));

srep(i,1,ans.size()) cout << ans[i] << endl;

return 0;

}

*1:a,b)\) を追加したとき，

頂点 \(a,b\) が既に同じ connected component に属していれば変化しない
そうでなければ，連結成分2つが 1つにくっつくので，\(-1\)個

実装
何も処理をしてない状態を含めて，(クエリの回数+1) 個の答えを配列に入れておく．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

ll n, m;

cin >> n >> m;

vvll to(n);

rep(i,m){

ll a,b; cin >> a >> b;

--a,--b;

if(a > b) swap(a,b);

to[a].push_back(b);

}

vll ans;

UnionFind<ll> uf(n);

ll c = 0;

ans.push_back(c);

drep(i,n){

c++;

for(auto a:to[i]){

if(!uf.same(a,i