题目描述

考虑离线做法,倒过来看这道题会发现容易得多,先存边,存点,倒叙遍历会发现是一个加边的过程,实时维护联通块即可

样例

blablabla

算法1

(由于并查集时间复杂度的优越性) $O(nlogn)$

#include<bits/stdc++.h>
#include<set>
#include<cstring>
#include<cstdio>
#define pii pair<int,int>
#define f first
#define s second
#include<deque>
#include<vector>
#include<algorithm>
#define mod 1000000007

#define ll long long
#define N 701000
using namespace std;

int e[N],ne[N],h[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m,k;
int fa[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void init(){
    for(int i=0;i<n;i++)fa[i]=i;
}
int mp[N];

int p[N];
int ans[N];
pii ask[N];
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=m-1;i>=0;i--){
        scanf("%d %d",&ask[i].f,&ask[i].s);
        add(ask[i].f,ask[i].s);
        add(ask[i].s,ask[i].f);
    }
    init();
    cin>>k;

    for(int i=k-1;i>=0;i--){
        scanf("%d",&p[i]);
        mp[p[i]]++;
    }
    int res=0;
    for(int i=0;i<m;i++){
        if(mp[ask[i].f]||mp[ask[i].s])continue;

        int fx=find(ask[i].f),fy=find(ask[i].s);
        if(fx!=fy){
            fa[fy]=fx;
        }

    }
    for(int i=0;i<n;i++){
        if(mp[i])continue;
        if(fa[i]==i)res++;
    }

    int cnt=k;
    ans[cnt--]=res;
    for(int i=0;i<k;i++){
        int u=p[i];
        res++;
        mp[u]=0;
        for(int j=h[u];~j;j=ne[j]){
            int v=e[j];
            if(mp[v])continue;
            int fx=find(u),fy=find(v);
            if(fx!=fy){
                fa[fy]=fx;
                res--;
            }

        }
        ans[cnt--]=res;
    }
    for(int i=0;i<=k;i++)
    cout<<ans[i]<<endl;
    return 0;
}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla