ZJ b570: 為什麼你們都喜歡撞來撞去的？

好久沒寫題目了.......

題目鏈接：https://zerojudge.tw/ShowProblem?problemid=b570
看過題目之後其實不難發現他是並查集
因為他是炸掉邊而不是加入邊
我們用並查集會很難維護他
但如果我們倒著加入邊是不是能得到一樣的效果呢？
所以實際的做法就是倒著加入邊，每次輸出的結果也是倒著的
將每次的結果加入一個stack中
最後輸出stack中全部的值
就是答案啦！

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

struct DSU

{

    vector<int> v;

    DSU(int x)

    {

        v.resize(x);

        for(int i=1;i<x;i++)

            v[i]=i;

    }

    int find(int x)

    {

        if(v[x]==x) return x;

        return v[x]=find(v[x]);

    }

    void Union(int x,int y)

    {

        v[find(x)]=find(y);

    }

};

int main()

{

    AC

    int n,m,Q,cnt=0;

    cin>>n>>m;

    DSU ds(n+1);

    vector<pair<int,int>> v(m+1);

    vector<bool> b(m+1),tmp(n+1);

    stack<int,vector<int>> s,q;

    for(int i=1;i<=m;i++)

        cin>>v[i].first>>v[i].second;

    cin>>Q;

    while(Q--)

    {

        int t;

        cin>>t;

        b[t]=1;

        q.emplace(t);

    }

    for(int i=1;i<=m;i++)

        if(!b[i]) ds.Union(v[i].first,v[i].second);

    for(int i=1;i<=n;i++)

    {

        int x=ds.find(i);

        if(!tmp[x]) tmp[x]=1,cnt++;

    }

    s.emplace(cnt);

    while(q.size()>1)

    {

        int cur=q.top();

        q.pop();

        if(ds.find(v[cur].first)!=ds.find(v[cur].second)) cnt--;

        ds.Union(v[cur].first,v[cur].second);

        s.emplace(cnt);

    }

    for(;s.size();s.pop())

        cout<<s.top()<<'\n';

}