bzoj1015: [JSOI2008]星球大战starwar-白红宇

bzoj1015: [JSOI2008]星球大战starwar

阅读量：5335 次

发布时间：2019-06-15

本文共 1553 字，大约阅读时间需要 5 分钟。

题解：并查集；

发现按顺序拆集合不行，就干脆反过来来合并集合；

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 using namespace std;13 const int maxn=404000;14 struct node{15 int y,next;16 }e[maxn];17 int linkk[maxn],len=0,fa[maxn],vis[maxn],q[maxn],g[maxn];18 int n,m,k;19 void insert(int x,int y){20 e[++len].y=y;21 e[len].next=linkk[x];22 linkk[x]=len;23 }24 int getfather(int x){25 int y=x,temp;26 while(fa[y]!=y)y=fa[y];27 while(y!=x){28 temp=fa[x];29 fa[x]=y;30 x=temp;31 }32 return y;33 }34 bool Union(int x,int y){35 x=getfather(x);y=getfather(y);36 if(x==y)return 0;37 fa[x]=y;return 1;38 }39 void work(){40 scanf("%d %d",&n,&m);int x,y;41 for(int i=1;i<=m;i++){42 scanf("%d %d",&x,&y);x++,y++;43 insert(x,y);insert(y,x);44 }45 scanf("%d",&k);46 for(int i=1;i<=k;i++){scanf("%d",&q[i]);q[i]++;vis[q[i]]=1;}47 for(int x=1;x<=n;x++){48 fa[x]=x;49 if(vis[x])continue;50 for(int i=linkk[x];i;i=e[i].next){51 if(vis[e[i].y])continue;52 Union(x,e[i].y);53 }54 }55 int ans=0;56 for(int i=1;i<=n;i++){57 fa[i]=getfather(i);58 if(fa[i]==i&&!vis[i])ans++;59 }60 for(int j=k;j>=1;j--){61 x=q[j];vis[x]=0;62 for(int i=linkk[x];i;i=e[i].next){63 if(vis[e[i].y])continue;64 if(Union(e[i].y,x))ans--;65 }66 g[j]=ans;67 }68 for(int i=1;i<=k;i++)printf("%d\n",g[i]);69 }70 int main(){71 work();72 return 0;73 }