BZOJ 1015: [JSOI2008]星球大战starwar（并查集求连通块+离线处理）

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,ll> pll;
 15 const int INF = 0x3f3f3f3f;
 16 const int maxn=200000+5;
 17 
 18 int n, m;
 19 int k;
 20 int tot;
 21 int cnt;
 22 int q[2*maxn];
 23 int p[2*maxn];
 24 int vis[2*maxn];
 25 int del[2*maxn];
 26 int ans[2*maxn];
 27 int head[2*maxn];
 28 
 29 struct node
 30 {
 31     int v,next;
 32 }e[2*maxn];
 33 
 34 void addEdge(int u,int v)
 35 {
 36     e[tot].v=v;
 37     e[tot].next=head[u];
 38     head[u]=tot++;
 39 }
 40 
 41 int Find(int x)
 42 {
 43     return x==p[x]?x:p[x]=Find(p[x]);
 44 }
 45 
 46 void update(int u)
 47 {
 48     for(int i=head[u];i!=-1;i=e[i].next)
 49     {
 50         int v=e[i].v;
 51         if(vis[v])  //如果v之前已经访问过了并且u和v不在同一连通块中，那么合并并且减少一个连通块
 52         {
 53             int x=Find(u);
 54             int y=Find(v);
 55             if(x!=y)  {p[x]=y;cnt--;}
 56         }
 57     }
 58 }
 59 
 60 int main()
 61 {
 62     //freopen("in.txt","r",stdin);
 63     while(~scanf("%d%d",&n,&m))
 64     {
 65         tot=0;
 66         memset(head,-1,sizeof(head));
 67         memset(del,0,sizeof(del));
 68         memset(vis,0,sizeof(vis));
 69         for(int i=0;i<n;i++)  p[i]=i;
 70         while(m--)
 71         {
 72             int u,v;
 73             scanf("%d%d",&u,&v);
 74             addEdge(u,v);
 75             addEdge(v,u);
 76         }
 77 
 78         scanf("%d",&k);
 79         for(int i=1;i<=k;i++)  {scanf("%d",&q[i]);del[q[i]]=1;}
 80 
 81         cnt=0;
 82         for(int i=0;i<n;i++)
 83         {
 84             if(!del[i])
 85             {
 86                 cnt++; //先把它单独作为一个连通块
 87                 update(i);
 88                 vis[i]=1;
 89             }
 90         }
 91 
 92         ans[k+1]=cnt;
 93         for(int i=k;i>=1;i--)  //加点
 94         {
 95             cnt++;
 96             update(q[i]);
 97             vis[q[i]]=1;
 98             ans[i]=cnt;
 99         }
100         for(int i=1;i<=k+1;i++)  printf("%d
",ans[i]);
101     }
102     return 0;
103 }