Star Wars 2019

AFoxOfZzr @ 2019-05-20 23:20:05

#include<iostream>
#include<cstdio>
#include<cstring>
#define man 520000
using namespace std;
int to[man],head[man],next[man],from[man];
int n,m,cnt,k,f[man],h[man],ans[man];
bool v[man];
inline void add(int x,int y){
    to[++cnt]=y;
    from[cnt]=x;
    next[cnt]=head[x];
    head[x]=cnt;
}
int find(int x){
    while(x!=f[x]) x=f[x]=f[f[x]];
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        int a;
        scanf("%d",&a);
        h[i]=a;
        v[a]=1;
    }
    for(int i=0;i<n;i++)
        f[i]=i;

    int tot=n-k;
    for(int i=1;i<=cnt;i++){
       if(!v[to[i]] and !v[from[i]]){
           if(find(to[i])!=find(from[i])){
             tot--;
             f[to[i]]=f[from[i]];
           }
       }
    }

    ans[k+1]=tot;

    //printf("\n%d\n",tot);

    for(int i=k;i>=1;i--){
        tot++;
        int u=h[i];
        v[u]=0;
        for(int l=head[u];l;l=next[l]){
            if(!v[to[l]] and find(to[l])!=find(u)){
                tot--;
                f[to[l]]=f[u];
                //printf("\n%d\n\n",tot);
            }
        }
     ans[i]=tot;
    }

    for(int i=1;i<=k+1;i++){
     printf("%d\n",ans[i]);
    }
    return 0;
}

by malloc_size @ 2019-05-21 06:55:52

2019版——AFoxOfZzr——1.0

by Luvwgyx @ 2019-05-21 09:19:10

你都来讨论版问了和看题解有啥区别呢？

by AFoxOfZzr @ 2019-05-21 09:34:07

@Luvwgyx 嗯嗯嗯？？？

by AFoxOfZzr @ 2019-05-21 09:39:40

自己调过来了，下面说一下错因，希望看到这个帖子的人引以为戒（看了题解后）

就像我连续三节政治都被提问然都未背过一样

1.要注意存储顺序和输出顺序和使用顺序；

2.要注意合并时直接合并到最底部， 上面f[to[i]]=f[from[i]];是错误的，应当要f[find(to[l])]=f[find(too)]；

3.注意恢复星球时要标记为恢复；

by AFoxOfZzr @ 2019-05-21 09:41:17

我开的空间有点大 ,而且还开的long long AC代码：

#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;
}