40分求调!!!

P1197 [JSOI2008] 星球大战

__Refine__ @ 2024-10-20 11:19:27


#include<bits/stdc++.h>

using namespace std;

struct bian
{
    int nxt,to,cme;
}b[401010];
int dian[401001],tot;
long long n,m,k,atc[400001],ans[400001];
int fa[400001],all;
bool book[400001];
int fnd(int x)
{
    return fa[x]==x?x:fa[x]=fnd(fa[x]);
}
inline void add(int x,int y)
{
    b[++tot].nxt=dian[x];
    b[tot].to=y;
    dian[x]=tot;
    b[tot].cme=x;
}
inline void solve(int x)
{   
    for(int i=dian[x];i;i=b[i].nxt)
    {
        int t=fnd(x);
        int r=fnd(b[i].to);
        if(t!=r&&book[b[i].to]==false)
        {
            fa[r]=t;
            all--;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&atc[i]);
        book[atc[i]]=true;
    }
    all=n-k;
    for(int i=1;i<=2*m;i++)
    {
        if(!book[b[i].cme]&&!book[b[i].to]&&fnd(b[i].cme)!=fnd(b[i].to))
        {
            all--;
            fa[b[i].cme]=fa[b[i].to];
        }
    }
    ans[k+1]=all;
    for(int i=k;i>=1;i--)
    {
        book[atc[i]]=false;
        all++;
        solve(atc[i]);
        ans[i]=all;
    }
    for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
    return 0;
}
```cpp

by cindyssx @ 2024-10-21 10:25:47

for(int i=1;i<=2*m;i++)
    {
        if(!book[b[i].cme]&&!book[b[i].to]&&fnd(b[i].cme)!=fnd(b[i].to))
        {
            all--;
            fa[b[i].cme]=fa[b[i].to];
        }
    }

修改赋值语句

for(int i=1;i<=2*m;i++)
    {
        if(!book[b[i].cme]&&!book[b[i].to]&&fnd(b[i].cme)!=fnd(b[i].to))
        {
            all--;
            fa[fnd(b[i].cme)]=fa[fnd(b[i].to)];
        }
    }

|