[Ural 1671][Disjoint Set][Offline] Anansi's Cobweb

原題連結
在線作法的話......不知道XD，LCT大概能做(?

離線作法的話非常經典，把所有操作讀入後反過來做，這樣刪除操作就變成了加邊操作，使用并查集就能輕鬆過~~

#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
struct Edge {int from,to,Do;};
const int maxn=100000+5;
int fa[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
vector<Edge> edges;
vector<int> query,ans;
int main()
{
    int Q,N,M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++) fa[i]=i;
    for(int i=0,a,b;i<M;i++)
    {
        scanf("%d%d",&a,&b);
        edges.push_back((Edge){a,b,1});
    }
    scanf("%d",&Q);
    for(int i=0;i<Q;i++)
    {
        int x;
        scanf("%d",&x);x--;
        query.push_back(x);
        edges[x].Do=0;
    }
    int cnt=N;
    for(int i=0;i<M;i++) if(edges[i].Do)
    {
        int u=findset(edges[i].from),v=findset(edges[i].to);
        if(u!=v) cnt--;
        fa[u]=v;
    }
    for(int i=Q-1;i>=0;i--)
    {
        ans.push_back(cnt);
        int u=findset(edges[query[i]].from),v=findset(edges[query[i]].to);
        if(u!=v) cnt--;
        fa[u]=v;
    }
    for(int i=Q-1;i>=0;i--) printf("%d%c",ans[i],i==0?'\n':' ');
}