不知道哪里错了

P1197 [JSOI2008] 星球大战

Cwling @ 2020-08-16 18:42:03

样例未过


#include <bits/stdc++.h>
#define MAXN 1000001 
using namespace std;
inline int read()
{
    int r=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
        f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
    return r*f;
}
struct p{
    int next,to,from;
}edge[MAXN];
int num_edge;
int head[MAXN];
int b[MAXN];
int f[MAXN];
int anss[MAXN];
void add(int from,int to)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].to=to;
    edge[num_edge].from=from;
    head[from]=num_edge;
}
int find(int x)
{
    if(f[x]!=x)
    f[x]=find(f[x]);
    return f[x];
}
void unionn(int x,int y)
{
    f[x]=y;
    return;
}
int ans;
int main() {
    int n=read(),m=read();
    for(int i=1;i<=n;++i)
    f[i]=i;
    for(int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    int k=read();
    ans=n-k;
    for(int i=1;i<=k;++i)
    {
        f[i]=read();
        b[f[i]]=true;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=head[i];j;j=edge[j].next)
        {
            int v=edge[j].to;
            if(!b[i]&&!b[v])
            {
                int k1=find(i),k2=find(v);
                if(k1!=k2)
                {
                    unionn(k1,k2);
                    ans--;
                }
            }
        }
    }
    anss[k+1]=ans;
    for(int i=k;i>=1;--i)
    {
        b[f[i]]=false;
        ans++;
        int k1=find(f[i]);
        for(int j=head[f[i]];j;j=edge[j].next)
        {
            int v=edge[j].to;
            if(!b[v])
            {
                int k2=find(v);
                if(k1!=k2)
                {
                    unionn(k1,k2);
                    ans--;
                }
            }
        }
        anss[i]=ans;
    }
    for(int i=1;i<=k+1;++i)
    cout<<anss[i]<<endl;
    return 0;
}

by Cwling @ 2020-08-16 20:14:19

救救孩子


|