【BZOJ 1015】【tyvj 3487】スターウォーズスターウォーズ

転送ドア1転送ドア2は前に书いてあります:考え方がありません:比较的に简単で、テーマを调べて、ちょうどするのは难しいです.私たちは考えて、逆さまに并べて、1つの星に参加するたびに、连れることができる辺を连结することに相当します.连通ブロックの数を调べてください.注意:2つの頂点が破壊されていなければ、操作コードを调べることができません.

#include"bits/stdc++.h"
using namespace std;
int tot=1,x,y,n,m,k,ans;
struct os
{
    int u,v,next;
}a[400010];
int father[400010],first[400010],q[400010],outs[400010];
bool flag[400010];
int in()
{
    int t=0;
    char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
    return t;
}
void add(int x,int y)
{
    a[++tot].u=x;
    a[tot].v=y;
    a[tot].next=first[x];
    first[x]=tot;
}
int find(int x)
{
    if (x!=father[x]) father[x]=find(father[x]);
    return father[x];
}
void unions(int x,int y)
{
    if (x!=y) father[x]=y,ans--;
}
main()
{
    n=in();m=in();
    for (int i=1;i<=m;i++)
    x=in(),y=in(),
    add(x,y),add(y,x);
    k=in();
    ans=n;
    for (int i=1;i<=k;i++)
    {
        q[i]=in();
        ans--;
        flag[q[i]]=1;
    }
    for (int i=1;i<=n;i++) father[i]=i; 
    for (int i=1;i<=n;i++)
    if (!flag[i])
    for (int j=first[i];j;j=a[j].next)
    if (!flag[a[j].v])
    unions(find(a[j].v),find(a[j].u));
    for (int i=k;i>=1;i--)
    {
        outs[i]=ans++;
        flag[q[i]]=0;
        for (int j=first[q[i]];j;j=a[j].next)
        if (!flag[a[j].v])
        unions(find(a[j].v),find(a[j].u));
    }
    printf("%d
",ans);
    for (int i=1;i<=k;i++)
    printf("%d
",outs[i]);
}