[JSOI2008][TYVJ P1824] 星球大战

描述

很久以前,在一个遥远的银河系……对反抗军来说,这是一个黑暗的时刻。虽然帝国军的终极武器“死亡星球”已经被摧毁,帝国的军队仍然把反抗军从隐藏的军事基地中赶出,并在整个银河系展开追逐。 

考虑到邪恶的帝国完全有能力在短时间内制造出“死亡星球”的替代品,为了避免被一次全部歼灭,反抗军的指挥官决定把部队分散在很多星球上。可是,这样会带来通讯上的问题。某些星球之间可以通过“以太”隧道直接通讯,而没有隧道相连的星球之间的通讯就需要其他星球帮忙转发。因此,只有两个星球之间存在一条由“以太”隧道拼接成的路径,它们才可以正常通讯。

银河历2008年4月1日凌晨,反抗军最担心的事情还是发生了。反抗军司令部收到间谍的秘密通知:帝国军成功制造出第二代“死亡星球”,并将依次摧毁如下星球(星球列表略)。指挥官希望迅速计算出每次攻击之后通讯网络的连通情况,即反叛军所占据的星球被分成了多少个连通支,从而帮助决定在何时发动反击。

输入格式

输入文件的第一行包含两个整数N (2 ≤ N ≤ 2M)和M (1 ≤ M ≤ 200,000),分别表示星球的数目和“以太”隧道的数目。星球用0到N – 1的整数编号。
接下来的M行,每行包含两个整数X和Y (0 ≤ X ≠ Y < N),表示星球X和星球Y之间有“以太”隧道,可以直接通讯。
接下来的一行包含一个整数K,表示将遭受攻击的星球的数目。
接下来的K行,每行一个整数,按照顺序列出了帝国军的攻击目标。这K个数互不相同,且都在0到N – 1的范围内。

输出格式

输出文件应该包含K + 1行,每行一个整数。
第一个整数表示开始时通讯网络的连通支个数。
接下来的第I (1 ≤ I ≤ K)个整数,表示在攻击列表上的第I个星球被摧毁后,通讯网络的连通支个数。

测试样例1

输入

8 13 
0 1 
1 6 
6 5 
5 0 
0 6 
1 2 
2 3 
3 4 
4 5 
7 1 
7 2 
7 6 
3 6 





输出






3
 
分析:求连通块个数,简单的并查集即可解决,不过要加以处理。由于并查集只能加点不能删点,可以采取离线倒序处理的方法解决。
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
using namespace std;  
int head[400001],next[400001],list[400001],a[400001],f[400001],ans[400001],n,m,k,sum,x,p,q,y,rest;  
bool visit[400001];  
int read()  
{  
    char c=getchar();   
    int a=0;  
    while (c<0||c>9) c=getchar();  
    while (c>=0&&c<=9)   
    {  
          a=a*10+c-0;  
          c=getchar();  
    }  
    return a;  
}  
int find(int i)  
{  
    int j=i,k=i,t;  
    while (f[j]!=j) j=f[j];  
    while (f[k]!=k)   
      
    {  
          t=k;  
          k=f[k];  
          f[t]=j;  
    }  
    return j;  
}  
void insert(int x,int y)  
{  
     sum++;  
     next[sum]=head[x];   
     head[x]=sum;  
     list[sum]=y;  
}  
int main()  
{  
    n=read();  
    m=read();  
    sum=0;  
    for (int i=1;i<=m;i++)  
    {  
        x=read();  
        y=read();  
        insert(x,y);  
        insert(y,x);  
    }  
    k=read();  
    memset(visit,1,sizeof(visit));  
    for (int i=1;i<=k;i++)   
    {  
        a[i]=read();  
        visit[a[i]]=0;  
    }    
    for (int i=0;i<n;i++) f[i]=i;  
    rest=n-k;  
    for (int i=0;i<n;i++)  
        if (visit[i])  
        {  
                     x=head[i];  
                     while (x!=0)  
                     {  
                           if (visit[list[x]])  
                               if (find(i)!=find(list[x]))  
                               {  
                                                          f[find(i)]=find(list[x]);  
                                                          rest--;  
                               }  
                           x=next[x];  
                     }  
        }  
    ans[k+1]=rest;  
    for (int i=k;i>=1;i--)  
    {  
        visit[a[i]]=true;  
        rest++;  
        p=find(a[i]);  
        x=head[a[i]];  
        while (x!=0)  
        {  
              if (visit[list[x]])   
              {  
                                 q=find(list[x]);  
                                 if (p!=q)   
                                 {  
                                           f[q]=p;  
                                           rest--;  
                                 }  
              }  
              x=next[x];  
        }  
        ans[i]=rest;  
    }  
    for (int i=1;i<=k+1;i++) printf("%d\n",ans[i]);  
    return 0;  
}  

#1: Accepted (0ms, 10540KiB)

#2: Accepted (686ms, 10548KiB)

#3: Accepted (171ms, 10544KiB)

#4: Accepted (0ms, 10548KiB)

#5: Accepted (561ms, 10544KiB)

#6: Accepted (62ms, 10544KiB)

#7: Accepted (140ms, 10544KiB)

#8: Accepted (748ms, 10548KiB)

#9: Accepted (670ms, 10548KiB)

 

PS:

最好用非递归并查集。

规模较大,建议使用读入优化。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。