BZOJ 1015 [JSOI2008]星球大战starwar (逆序并查集）

 1 #include<bits/stdc++.h> 2 #define se second 3 #define fi first 4 #define ll long long 5 #define ls l,m,rt<<1 6 #define rs m+1,r,rt<<1|1 7 #define Pii pair<int,int> 8 #define pb push_back 9 #define fio ios::sync_with_stdio(false);cin.tie(0)10 using namespace std;11 const double pi=acos(-1.0);12 const int N=1e6+5;13 using namespace std;14 int fa[N];15 int tot;16 struct node{17 ????int u,v;18 }q[200010];19 int a[N];20 bool vis[N];21 int ans[N];22 vector<int>un[N];23 void init (int x){24 ????for(int i=0;i<=x;i++){25 ????????fa[i]=i;26 ????}27 }28 int findfa(int x){29 ????return fa[x]==x?x:fa[x]=findfa(fa[x]);30 }31 void unite(int x,int y){32 ????x=findfa(x);33 ????y=findfa(y);34 ????if(x!=y){35 ????????fa[y]=x;36 ????????tot--;//不同联通块相连则联通块数目减一37 ????}38 }39 40 int main(){41 ????int n,m;42 ????scanf("%d %d",&n,&m);43 ????init(n);44 ????for(int i=0;i<m;i++){45 ????????scanf("%d %d",&q[i].u,&q[i].v);46 ????}47 ????int k;48 ????scanf("%d",&k);49 ????for(int i=1;i<=k;i++){50 ????????scanf("%d",&a[i]);51 ????????vis[a[i]]=1;52 ????}53 ????tot=n-k;54 ????for(int i=0;i<m;i++){55 ????????if(vis[q[i].u]||vis[q[i].v]){// 如果一边是被拆掉的，则将两个点互相对方的不可行数组中（双向存边），否则直接联边56 ????????????un[q[i].u].pb(q[i].v);57 ????????????un[q[i].v].pb(q[i].u);58 ????????}59 ????????else {60 ????????????unite(q[i].u,q[i].v);61 ????????}62 ????}63 ????ans[k+1]=tot;64 ????for(int i=k;i>0;i--){65 ????????tot++;//将该点设为未被打击点，并将联通块加一，因为多出来一个未被打击的联通块66 ????????int m=a[i];67 ????????vis[m]=0;68 ????????for(int j=0;j<un[m].size();j++){69 ????????????if(!vis[un[m][j]])70 ????????????????unite(m,un[m][j]);71 ????????}72 ????????ans[i]=tot;73 ????}74 ????for(int i=1;i<=k+1;i++)printf("%d\n",ans[i]);75 ????return 0;76 }