P1197 [JSOI2008]星球大战

-------------------------------------

这可真是星球大战

--------------------------------------

链接： P1197

-----------------------------------------

看一下这道题，如果我们正着做，每摧毁一个后就重新建图，判连通。这样肯定工程浩大且超时，我们就要换个方法了。

为什么不倒着做呢？我们先求出来最后剩下的数量，然后倒着恢复一个又一个的星球，并且重新判断这个星球的连通状况。

欸，这样好像简单了许多

----------------------------------------

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,m,k;
 7 const int maxn = 400010;
 8 int fa[maxn];//并查集判连通 
 9 int p;
10 int head[maxn];
11 int planet[maxn];//第i次炸了哪个星球 
12 int ans[maxn];
13 struct l{
14     int from;
15     int to;
16     int next;
17 }b[maxn];
18 int x,y;
19  void build(int f,int t){
20     p++;
21     b[p].next=head[f];
22     b[p].from=f;
23     b[p].to=t;
24     head[f]=p;
25 }//链表存图 
26 inline int find(int x){
27     if(fa[x]==x)
28     return x;
29     else
30     return fa[x]=find(fa[x]);//查询
31     //路径压缩 
32 }
33 bool boom[maxn];//是否已经被炸 
34 int main(){
35     scanf("%d%d",&n,&m);
36     for(int i=0;i<=n;++i){
37         fa[i]=i;
38         head[i]=-1;//注意，有0号星球 
39     }
40     for(int i=1;i<=m;++i){
41         scanf("%d%d",&x,&y);
42 
43         build(x,y);
44         build(y,x);//无向图 
45     }
46     scanf("%d",&k);
47     for(int i=1;i<=k;++i){
48         scanf("%d",&planet[i]);
49         boom[planet[i]]=1;//记录被炸的星球和什么时候被炸 
50     }
51     int le=n-k;//在全部炸完后的剩余 
52     //我们假设全部都是不连通 
53     for(int i=1;i<=2*m;++i){
54         if((!boom[b[i].from])&&(!boom[b[i].to])&&(find(b[i].from)!=find(b[i].to)))
55         {//如果两端没有被炸且不是已经联通 
56             le--;//连通块减一 
57             fa[find(b[i].from)]=fa[find(b[i].to)];
58         }//检查联通，合并 
59     }
60     ans[k+1]=le;
61     for(int t=k;t>=1;--t){//我们来逐渐修复 
62         int u=planet[t];
63         le++;//假定不连通 
64         boom[u]=0;//恢复 
65         for(int j=head[u];j!=-1;j=b[j].next){//遍历 
66                 if(boom[b[j].to]==0&&(fa[find(u)]!=fa[find(b[j].to)]))//检查 
67                 {
68                     le--;//连通块减一，合并 AC
69                     fa[find(b[j].to)]=fa[find(u)];
70                 }
71         }
72         ans[t]=le;//统计这次后的数量 
73     }
74     for(int i=1;i<=k+1;++i)
75     printf("%d
",ans[i]);//输出 
76     return 0; 
77 }