90pts求助,#9wa

P1197 [JSOI2008] 星球大战

mmdxmakioi @ 2023-01-31 18:50:39

#include<cstdio>
#include<vector>
using namespace std;
int m;
int n;
vector<int> G[400005];
bool flag[400005];
int del[400005];
int fa[400005];
int k;
int find(int x)
{
    if(fa[x]!=x)
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy;
    return;
}
void init()
{
    int i,j;
    for(i=0;i<=400000;i++)
    {
        fa[i] = i;
    }
}
int ans[400005];
int main()
{
    init();
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    scanf("%d",&k);
    int tot = n-k;
    for(i=1;i<=k;i++)
    {
        scanf("%d",&del[i]);
        flag[del[i]] = true;
    }
    for(i=1;i<=m;i++)
    {
        if(flag[i])
        {
            continue;
        }
        vector<int>::iterator it;
        for(it = G[i].begin();it != G[i].end();it ++)
        {
            int y = *it;
            if(flag[y])
            {
                continue;
            }
            else
            {
                if(find(i)!=find(y))
                {
                    tot--;
                    merge(i,y);
                }
            }
        }
    }

    ans[k+1] = tot;
    for(i=k;i>=1;i--)
    {
        tot++;
        flag[del[i]] = false;
        vector<int>::iterator it;
        for(it = G[del[i]].begin();it != G[del[i]].end();it ++)
        {
            int y = *it;
            if(flag[y])
            {
                continue;
            }
            else
            {
                if(find(y) == find(del[i]))
                {
                    continue;
                }
                else
                {
                    merge(del[i],y);
                    tot--;
                }
            }
        }
        ans[i] = tot;
    }
    for(i=1;i<=k+1;i++)
    {
        printf("%d\n",ans[i]);
    }
}

by wula_miao @ 2023-03-11 20:33:20

main中第三个for循环范围是n不是m


|