90分求助。超时一个点

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 KokiNiwa @ 2020-02-22 13:54:02

写按秩合并呀

by Lube @ 2020-02-22 16:50:25

@skicean 感谢

by Lube @ 2020-02-22 17:11:56

@skicean 还是挂了

by Lube @ 2020-02-22 17:12:20

#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],rank[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 read()
{
    int x=0,f=1;
    char c;
    c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>=10)write(x/10);
    putchar(x%10+(1<<5)+(1<<4));
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)jh[i]=i;
    for(int i=1;i<=m;i++)
    {
        int g1,g2;
        g1=read();g2=read();
        tot++;to[tot]=g2;next[tot]=head[g1];head[g1]=tot;
        tot++;to[tot]=g1;next[tot]=head[g2];head[g2]=tot;
    }
    bre=read();
    for(int i=1;i<=bre;i++)
    {
        mark[i]=read();
        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--;
                        if(rank[x]<rank[y])jh[x]=y;
                        else
                        {
                            jh[y]=x;
                            if(rank[x]==rank[y])rank[x]++;
                        }
                    }
                }
            }
        }
    }
    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--;
                    if(rank[x]<rank[y])jh[x]=y;
                    else
                    {
                        jh[y]=x;
                        if(rank[x]==rank[y])rank[x]++;
                    }
                }
            }
        }
        tal++;ans[tal]=sum;
    }
    for(int i=tal;i>=1;i--){write(ans[i]);putchar('\n');}
}

@skicean

by KokiNiwa @ 2020-02-22 19:47:50

@blayt 您rank初始化呢。。。

by Lube @ 2020-02-23 12:01:27

@skicean ……rank数组难道初值不是0么……

by KokiNiwa @ 2020-02-23 12:03:30

@blayt 我好像失误了...（我写按秩合并都是按大小写的...所以rank需要初始化，对不起哈）不过您也可以试试按照大小搞按秩合并。

by Lube @ 2020-02-23 12:04:08

@skicean 好的谢谢

by Lube @ 2020-02-23 16:22:14

@skicean 问题不是并查集。数组开成原来的好几倍大就AC了

by KokiNiwa @ 2020-02-23 17:04:39

@blayt 我没看题就帮您胡调。。。