星球大战-题解

查看原题请戳这里

我没看过电影qwq…… 刚开始看到这个题，觉着可以用Floyd去做，时间复杂度为n^3…… 于是……

我们还是用并查集好了

当然了，如果我们在每次删去一个点后就跑一遍并查集去统计联通块的数量，那么一定会超时的。 所以，我们要用另一种方法……

倒着做！

然后，我们先把所有将被干掉的星球的状态都先记为死亡，然后一个个的复活并用所有与该点有关的边去更新联通块的数量。 附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long

using namespace std;
int n,m,cnt,k,x,y,f[400005],head[400005],kill[400005],live[400005],ans[400005];
struct Edge{
    int to,next;
}edge[400005];
void add(int a,int b)
{
    edge[++cnt].to = b;
    edge[cnt].next = head[a];
    head[a] = cnt;
}
int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
void work(int x,int y)
{
    if(find(x) != find(y)) f[find(x)] = f[find(y)];
}
int main()
{
    scanf(“%d%d”,&n,&m);
    for(register int i = 1; i <= n; i++) f[i] = i;
    for(register int i = 1; i <= m; i++)
    {
        scanf(“%d%d”,&x,&y);
        x ++; y ++;
        add(x,y);
        add(y,x);
    }
    scanf(“%d”,&k);
    for(register int i = k; i > 0; i–)
    {
        scanf(“%d”,&kill[i]);
        kill[i] ++;
        live[kill[i]] = 1;
    }
    cnt = n;
    for(register int i = 1; i <= n; i++)
        if(!live[i])
            for(register int j = head[i]; j; j = edge[j].next)
                if(!live[edge[j].to])
                    if(find(i) != find(edge[j].to))
                    {
                        cnt –;
                        work(i,edge[j].to);
                    }
    cnt = cnt - k;
    ans[1] = cnt;
    for(register int i = 1; i <= k; i++)
    {
        live[kill[i]] = 0;
        cnt ++;
        for(register int j = head[kill[i]]; j; j = edge[j].next)
                if(!live[edge[j].to])
                    if(find(kill[i]) != find(edge[j].to))
                    {
                        cnt –;
                        work(kill[i],edge[j].to);
                    }
        ans[i + 1] = cnt;
    }
    for(register int i = k + 1; i > 0; i–) printf(“%d\n”,ans[i]);
    return 0;
}