样例已过，0分，悬赏关注，谢谢

lcbridge @ 2023-01-24 21:21:16

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,k;
vector <int> G[200005];
int del[400005],fa[400005],ans[400005];
bool vis[400005];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<G[x].size();i++){
        if(!vis[G[x][i]]){
            int fx=find(x);
            int fy=find(G[x][i]);
            if(fx!=fy)fa[fy]=fx;
            dfs(G[x][i]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d",&del[i]);
        vis[del[i]]=1;
    } 
    int sum=0;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            ++sum;
            dfs(i);
        }
    }
    ans[k+1]=sum;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=k;i++)vis[del[i]]=1;
    for(int i=k;i>=1;i--){
        int x=del[i];
        sum++;
        for(int j=0;j<G[x].size();j++){
            if(!vis[G[x][j]]){
                int fx=find(x);
                int fy=find(G[x][j]);
                sum-=(fx!=fy);
                fa[fy]=fx;
            }
        }
        ans[i]=sum;
    }
    for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]);
    return 0;
} 

by lcbridge @ 2023-01-24 21:31:01

改了一下20分了

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,k;
vector <int> G[2000005];
int del[4000005],fa[4000005],ans[4000005];
bool vis[4000005];
int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
void dfs(int x){
    vis[x]=1;
    for(int i=0;i<G[x].size();i++){
        if(!vis[G[x][i]]){
            int fx=find(x);
            int fy=find(G[x][i]);
            if(fx!=fy)fa[fy]=fx;
            dfs(G[x][i]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d",&del[i]);
        vis[del[i]]=1;
    } 
    int sum=0;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            ++sum;
            dfs(i);
        }
    }
    ans[k+1]=sum;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=k;i++)vis[del[i]]=1;
    for(int i=k;i>=1;i--){
        int x=del[i];
        vis[x]=0;
        sum++;
        for(int j=0;j<G[x].size();j++){
            if(!vis[G[x][j]]){
                int fx=find(x);
                int fy=find(G[x][j]);
                sum-=(fx!=fy);
                fa[fy]=fx;
            }
        }
        ans[i]=sum;
    }
    for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]);
    return 0;
} 

by ReTF @ 2023-01-24 21:33:03

你确定你这个复杂度是对的吗。。。

by lcbridge @ 2023-01-24 21:35:19

@ReanimateThroughFire 对的呀

记录

by ReTF @ 2023-01-24 21:42:57

@Super_Dabubu 看起来很对，不知道是哪的问题

by 橙橙like海绵 @ 2023-08-29 09:00:19

@ReTF 我跟你错的一样，不知道哪里的问题orz