P1197 [JSOI2008]星球大战

思路：并查集+倒序操作

提交：1次

题解：把正向的摧毁换成逆向的加边，用并查集维护连通块数量就好了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define R register int
using namespace std;
const int N=400010;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
struct node{
    int u,v,rk;
    #define u(i) e[i].u
    #define v(i) e[i].v
    #define rk(i) e[i].rk
    bool operator <(const node& y)const{return rk<y.rk;}
}e[N];
int n,m,k,t=1,cnt,fa[N],d[N],vis[N],ans[N],mem[N];
int getf(int x) {return x==fa[x]?x:fa[x]=getf(fa[x]);}
inline void merge(int u,int v) {
    u=getf(u),v=getf(v);
    if(u!=v) fa[u]=v,--cnt;
}
signed main() {
    n=g(),m=g(); 
    for(R i=1;i<=n;++i) fa[i]=i;
    for(R i=1;i<=m;++i) u(i)=g(),v(i)=g();
    k=g();
    for(R i=1,x;i<=k;++i) x=g(),mem[x]=k-i+1;
    for(R i=1;i<=m;++i) rk(i)=max(mem[u(i)],mem[v(i)]);
    sort(e+1,e+m+1); cnt=n;
    for(R i=0;i<=k;++i) {
        while(rk(t)==i) merge(u(t),v(t)),++t;
        ans[i]=cnt+i-k;
    }
    for(R i=k;i>=0;--i) printf("%d
",ans[i]);
}

---

2019.07.22