2019版——AFoxOfZzr——1.0
by malloc_size @ 2019-05-21 06:55:52
~~你都来讨论版问了和看题解有啥区别呢？~~
by Luvwgyx @ 2019-05-21 09:19:10
@[Luvwgyx](/space/show?uid=43012)
嗯嗯嗯？？？
by AFoxOfZzr @ 2019-05-21 09:34:07
自己调过来了，下面说一下错因，希望看到这个帖子的人引以为戒（看了题解后）
~~就像我连续三节政治都被提问然都未背过一样~~
1.要注意存储顺序和输出顺序和使用顺序；
2.要注意合并时直接合并到最底部，
上面`f[to[i]]=f[from[i]];`是错误的，应当要`f[find(to[l])]=f[find(too)]`；
3.注意恢复星球时要标记为恢复；
by AFoxOfZzr @ 2019-05-21 09:39:40
~~我开的空间有点大~~ ,~~而且还开的long long~~
AC代码：
```cpp
#include<iostream>
#include<cstdio>
#define lint long long
#define re register
using namespace std;
const int man=4e5+4;
lint to[man],head[man],from[man],next[man];
lint f[man],h[man],ans[man];
lint n,m,cnt,tot,k;
bool v[man];
inline void add(lint x,lint y){
to[++cnt]=y;
from[cnt]=x;
next[cnt]=head[x];
head[x]=cnt;
}
lint find(lint x){
while(x!=f[x]) x=f[x]=f[f[x]];
return x;
}
int main(){
scanf("%lld%lld",&n,&m);
for(re lint i=0;i<n;i++){
f[i]=i;
head[i]=-1;
}
for(re lint i=1;i<=m;i++){
lint a,b;
scanf("%lld%lld",&a,&b);
add(a,b);add(b,a);
}
scanf("%lld",&k);
for(re lint i=k;i>=1;i--){
int a;
scanf("%lld",&a);
h[i]=a;
v[a]=1;
}
tot=n-k;
for(re lint i=1;i<=cnt;i++){
if(v[to[i]]==0 and v[from[i]]==0){
if(find(to[i])!=find(from[i])) {
tot--;
f[find(to[i])]=f[find(from[i])];
}
}
}
ans[k+1]=tot;
for(re lint i=1;i<=k;i++){
lint too=h[i];
v[too]=0;
tot++;
for(re lint l=head[too];l!=-1;l=next[l]){
// printf("len\n%d\n",l);
if(v[to[l]]==0 and f[find(too)]!=f[find(to[l])]){
tot--;
f[find(to[l])]=f[find(too)];// 要更新到根
}
}
ans[i]=tot;
// printf("\n%d\n",ans[i]);
}
for(re lint i=k;i>=1;i--)
printf("%lld\n",ans[i]);
printf("%lld\n",ans[k+1]);
return 0;
}
```
by AFoxOfZzr @ 2019-05-21 09:41:17