90分求助。超时一个点

P1197 [JSOI2008] 星球大战

Lube @ 2020-02-22 13:52:26

#include<bits/stdc++.h>
using namespace std;
bool vis[200005],pd[200005];
int head[200005],next[800005],to[800005],tot;
int mark[200005];
int jh[200005];
int ans[200005],tal,sum,n,m,bre;
int find(int num)
{
    if(num==jh[num])return num;
    return jh[num]=find(jh[num]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)jh[i]=i;
    for(int i=1;i<=m;i++)
    {
        int g1,g2;
        scanf("%d%d",&g1,&g2);
        tot++;to[tot]=g2;next[tot]=head[g1];head[g1]=tot;
        tot++;to[tot]=g1;next[tot]=head[g2];head[g2]=tot;
    }
    scanf("%d",&bre);
    for(int i=1;i<=bre;i++)
    {
        scanf("%d",&mark[i]);
        vis[mark[i]]=true;
    }
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            sum++;
            int x,y;
            for(int j=head[i];j;j=next[j])
            {
                int g2=to[j];
                if(!vis[g2])
                {
                    y=find(g2);x=find(i);
                    if(x!=y)
                    {
                        sum--;
                        jh[x]=y;
                    }
                }
            }
        }
    }
    tal++;ans[tal]=sum;
    for(int i=bre;i>=1;i--)
    {
        int nm;nm=mark[i];vis[nm]=false;sum++;
        int x,y;
        for(int j=head[nm];j;j=next[j])
        {
            int g2=to[j];
            if(!vis[g2])
            {
                x=find(nm);
                y=find(g2);
                if(x!=y)
                {sum--;jh[x]=y;}
            }
        }
        tal++;ans[tal]=sum;
    }
    for(int i=tal;i>=1;i--)printf("%d\n",ans[i]);
}

by gdb1234 @ 2020-04-01 07:55:54

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}


上一页 |