URAL/1671

来自"NOCOW"

并查集的简单应用。

#include <iostream>
using namespace std;
int n,m,tot=0,Q,x[100001],y[100001],ask[100001];
int ans[100001],f[100001];
bool used[100001]={false};
inline int find(int t)
{
    if (f[t] == t)  return t;
    return f[t]=find(f[t]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)
        scanf("%d%d",x+i,y+i);
    scanf("%d",&Q);
    for (int i=1;i<=Q;++i)
    {
        scanf("%d",ask+i);
        used[ask[i]]=true;
    }
    for (int i=1;i<=n;++i)  f[i]=i;
    for (int i=1;i<=m;++i)
        if (!used[i])
        {
            int a=find(x[i]),b=find(y[i]);
            if (a != b)
                f[a]=b;
        }
    for (int i=1;i<=n;++i)
        if (f[i] == i)
            ++tot;
    for (int i=Q;i>0;--i)
    {
        int a=find(x[ask[i]]),b=find(y[ask[i]]);
        ans[i]=tot;
        if (a != b)
        {
            f[a]=b;
            --tot;
        }
    }
    for (int i=1;i<Q;++i)
        printf("%d ",ans[i]);
    printf("%d\n",ans[Q]);
    return 0;
}
//by zzy