星球大戰 bzoj1015 洛谷1197 JSOI2008

        本蒟蒻蒟蒻竟然也寫部落格了！我之前看過一些神犇在CSDN上的部落格，覺得諸位神犇十分厲害，orz，然而forever_shi還是個一道各省省選都沒寫過的蒟蒻。本是我的第一篇部落格，紀念我A掉的第一道bzoj的題目，并紀念我A掉的第一道各省的往年省選題，雖然這道題對于許多神犇來說十分簡單。如有錯誤請各位神犇指正。

好了，進入正題，題意是給一堆點，有若幹邊把他們相連，每次要删去一個點及所有與之相連的邊，求連通塊個數，并輸出一開始時的連通塊個數。

        乍一看這個題好像可以并查集，但是要删點不會是什麼lct之類的吧？然後發現似乎沒法用lct(因為我不會，而且似乎也不能用)，那就果斷并查集。但是并查集不支援删改操作，于是我最初想了個每次修改都重新跑一遍并查集，發現複雜度爆表。。。

        突然靈機一動，有的題目正向做不容易做時可以逆向考慮。那麼可以發現從最後要删的全删了的情況往前依次連邊就可以使用并查集維護了，維護的時候有一些小細節，我覺得我寫得挺麻煩的，但是我覺得本題的關鍵還是在逆向考慮上，其他的都是細節問題。

        下面貼一下AC代碼。（forever_shi并不追求代碼寫得“好看”，是以代碼醜，而且基本不去寫快讀）。

#include <bits/stdc++.h>

using namespace std;

struct node

{

 int next,to;

}e[400001];

int n,m,k,head[400001],cnt,book[400001],a[400001],f[400001],sum[400010];

int ji[400001],fan[400001];

void add(int from,int to)

{

 e[++cnt].next=head[from];

 e[cnt].to=to;

 head[from]=cnt;

}

int getr(int x)

{

 if(x==f[x])

 return x;

 else

 {

  f[x]=getr(f[x]);

  return f[x];

 }

}

void charu(int x,int y)

{

 int rx=getr(x),ry=getr(y);

 if(rx!=ry)

 {

  f[rx]=ry;

 }

 return;

}

int query(int x,int y)

{

 int rx=getr(x),ry=getr(y);

 if(rx!=ry)

 {

  f[rx]=ry;

  return 1;

 } 

 else

 return 0; 

}

int main()

{

 scanf("%d%d",&n,&m);

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

 {

  int x,y;

  scanf("%d%d",&x,&y);

  add(x,y);

  add(y,x);

 }

 scanf("%d",&k);

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

 {

  scanf("%d",&book[i]);

  fan[book[i]]=i;

  a[book[i]]=1;

 }

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

 f[i]=i;

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

 {

  if(a[i]==0)

  {

   for(int j=head[i];j;j=e[j].next)

   {

    if(a[e[j].to]==0)

    charu(e[j].to,i);

   }

  }

 }

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

 {

  if(a[i]==0)

  ji[getr(i)]=1;

 }

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

 {

  if(ji[i]==1)

  sum[k+1]++;

 }

 for(int i=k;i>=1;i--)

 {

  int x=book[i];

  sum[i]=sum[i+1]+1;

  for(int j=head[x];j;j=e[j].next)

  {

   if((a[e[j].to]==0)||(fan[e[j].to]>i))

   {

    sum[i]-=query(e[j].to,x);

   }   

  }  

 }

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

 printf("%d\n",sum[i]);

 return 0;

}