30分，TLE，求助！

王紫烨 @ 2019-12-07 22:56:11

//预处理命令
#include <bits/stdc++.h>
using namespace std;

//声明变量和结构体
int n,m,u,v,k,ans[400010]={0};
//经过深思熟虑，决定使用链式前向星
struct SIDE{
    int next,ed;
    SIDE(void){
        next=ed=-1;
    }
}si[400010];
int hd[400010],tot=0,dlt[400010];
bool ign[400010],vis[400010];

//声明函数
void addside(int x,int y){//用于添加无向边
    si[tot].ed=y;
    si[tot].next=hd[x];
    hd[x]=tot++;
    si[tot].ed=x;
    si[tot].next=hd[y];
    hd[y]=tot++;
}
int bfs(int x){
    int q,k,an=1;
    queue<int> qu;
    qu.push(x);
    vis[x]=1;
    while(qu.size()){
        q=qu.front();
        qu.pop();
        k=hd[q];
        while(k!=-1){
            if(!ign[si[k].ed]&&!vis[si[k].ed]){
                vis[si[k].ed]=1;
                qu.push(si[k].ed);
                ++an;
            }
            k=si[k].next;
        }
    }
    return an;
}

//main()函数，请从此处开始阅读
int main(){

    //输入
    scanf("%d%d",&n,&m);
    memset(hd,-1,4*n+16);
    for(int i=0;i<m;++i){
        scanf("%d%d",&u,&v);
        addside(u,v);
    }
    scanf("%d",&k);
    for(int i=0;i<k;++i){
        scanf("%d",&u);
        dlt[i]=u;
        ign[u]=1;
    }

    //处理
    for(int i=0;i<n;++i){
        if(!ign[i]&&!vis[i])ans[0]++,bfs(i);
    }
    for(int i=k-1;i>=0;--i){
        memset(vis,0,n+4);
        ans[k-i]=ans[k-i-1]+1;
        for(int j=hd[dlt[i]];j!=-1;j=si[j].next){
            if(!ign[si[j].ed]&&!vis[si[j].ed])ans[k-i]--,bfs(si[j].ed);
        }
        ign[dlt[i]]=0;
    }

    //输出
    for(int i=k;i>=0;--i){
        cout<<ans[i]<<endl;
    }

    return 0;
}

by 王紫烨 @ 2019-12-07 22:57:12

太慢了吧
我可是使用了链式前向星的呀
要读入优化吗
所有超时点都在1.20s

by RinkaSnow @ 2019-12-07 23:06:23

@王紫烨

停在1.2s因为时间到了强行结束程序，复杂度有问题啊

by 王紫烨 @ 2019-12-08 10:48:41

谢谢,那么哪里可以优化呢?

by 王紫烨 @ 2019-12-08 11:45:10

好啦，谢谢各位，此题已通过！
（天哪，并查集都写在那里了还忘了用，我是不是zz）
顺便把标准代码贴上来！

//预处理命令
#include <bits/stdc++.h>
using namespace std;

//声明变量和结构体
int n,m,u,v,k,ans[400010]={0},tem;//分别是点数,边数,两个临时变量,打击规模和答案集合,临时变量 
//经过深思熟虑，决定使用链式前向星
struct SIDE{
    int next,ed;
    SIDE(void){
        next=ed=-1;
    }
}si[400010];//边集 
int hd[400010],tot=0,dlt[400010],bin[400010];//单点首个边,临时边数,删除的点,并查集 
bool ign[400010];//删除点打表 

//声明函数
void addside(int x,int y){//用于添加无向边
    si[tot].ed=y;
    si[tot].next=hd[x];
    hd[x]=tot++;
    si[tot].ed=x;
    si[tot].next=hd[y];
    hd[y]=tot++;
}
int get(int x){
    return (bin[x]==x)?x:bin[x]=get(bin[x]);
}
inline bool merge(int x,int y){
    int x1=get(x),y1=get(y);
    if(x1==y1)return false;
    bin[x1]=y1;
    return true;
}

//main()函数，请从此处开始阅读
int main(){

    //输入
    scanf("%d%d",&n,&m);
    memset(hd,-1,4*n+16);
    memset(bin,-1,4*n+16);
    for(int i=0;i<m;++i){
        scanf("%d%d",&u,&v);
        addside(u,v);
    }
    scanf("%d",&k);
    for(int i=0;i<k;++i){
        scanf("%d",&u);
        dlt[i]=u;
        ign[u]=1;
    }

    //处理
    for(int i=0;i<n;++i){
        bin[i]=i;
    }
    ans[0]=n;
    for(int i=0;i<n;++i){
        if(ign[i]){
            ans[0]--;
            continue;
        }
        tem=hd[i];
        while(tem!=-1){
            if(!ign[si[tem].ed]){
                if(merge(i,si[tem].ed))--ans[0];
            }
            tem=si[tem].next;
        }
    }
    for(int i=k-1;i>=0;--i){
        ans[k-i]=ans[k-i-1]+1;
        for(int j=hd[dlt[i]];j!=-1;j=si[j].next){
            if(ign[si[j].ed])continue;
            if(merge(dlt[i],si[j].ed))--ans[k-i];
        }
        ign[dlt[i]]=false;
    }

    //输出
    for(int i=k;i>=0;--i){
        cout<<ans[i]<<endl;
    }

    return 0;
}
//抱歉主体部分没注释

by 王紫烨 @ 2019-12-08 11:46:39

我 没 开 O2!
并查集使我们充满了决心！