bzoj 1015: [JSOI2008]星球大战starwar

要细心

 

/**************************************************************    Problem: 1015    User: lxy8584099    Language: C++    Result: Accepted    Time:1596 ms    Memory:19964 kb****************************************************************/ /*    时光倒流      本来是拆点      但是我们按时间从后到前     加点 计算 缩点     那啥 1<=n<=2*m是什么。。。     看错范围一直RE      合并的时候要带上get (忘了带一直WA */#include<cstdio>using namespace std;const int N=400050;struct pp {int v,nxt;}e[N<<2];int fa[N],n,m,k,tot,head[N],cut[N],ans[N];bool vis[N];int get(int x){    return (x==fa[x])?(x):(fa[x]=get(fa[x]));}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) fa[i]=i;    for(int i=1,u,v;i<=m;i++)    {        scanf("%d%d",&u,&v);u++;v++;        e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;        e[++tot].nxt=head[v];head[v]=tot;e[tot].v=u;    }    scanf("%d",&k); int now=n-k;    for(int i=1;i<=k;i++)     {        scanf("%d",&cut[i]);cut[i]++;vis[cut[i]]=1;    }    for(int u=1;u<=n;u++) if(!vis[u])    {        for(int j=head[u];j;j=e[j].nxt)        {            int v=get(e[j].v);            if(vis[v]||get(u)==v) continue;            fa[v]=get(u);now--;        }    }    for(int i=k;i>=1;i--)    {        ans[i]=now; now++; int u=cut[i]; vis[u]=0;        for(int j=head[u];j;j=e[j].nxt)        {            int v=get(e[j].v);            if(vis[v]||u==v) continue;            fa[v]=u;now--;        }    } ans[0]=now;    for(int i=0;i<=k;i++) printf("%d\n",ans[i]);    return 0;}

 

相关文章