P1197-[JSOI2008]星球大战

Myth丶恋晨 2023-06-01 08:47 40阅读 0赞

1 #include <bits/stdc++.h>
      2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      4 #define INF 0x3f3f3f3f
      5 #define MOD 1000000007
      6 #define pb push_back
      7 typedef long long ll;
      8 using namespace std;
      9 inline ll read()
     10 {
     11     ll ans = 0;
     12     char ch = getchar(), last = ' ';
     13     while(!isdigit(ch)) last = ch, ch = getchar();
     14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     15     if(last == '-') ans = -ans;
     16     return ans;
     17 }
     18 inline void write(ll x)
     19 {
     20     if(x < 0) x = -x, putchar('-');
     21     if(x >= 10) write(x / 10);
     22     putchar(x % 10 + '0');
     23 }
     24 
     25 const int maxn = 400033;
     26 int par[maxn]; 
     27 int high[maxn]; 
     28 int cnt = 0;
     29 void init(int n)
     30 {
     31     _for(i,0,n)
     32     {
     33         par[i] = i;
     34         high[i] = 0;
     35     }
     36 } 
     37 
     38 int find(int x)
     39 {
     40     return par[x] == x ? x : par[x] = find(par[x]);
     41 }
     42 
     43 void unite(int x,int y)
     44 {
     45     x = find(x);y = find(y);
     46     if(x==y) return ;
     47     cnt --;
     48     if(high[x]<high[y])
     49         par[x] = y;
     50     else
     51     {
     52         par[y] = x;
     53         if(high[x]==high[y])
     54             high[x] ++;
     55     }
     56 }
     57 
     58 bool same(int x,int y)
     59 {
     60     return find(x) == find(y);
     61 }
     62 int N,M,K; 
     63 vector<int> G[400003];
     64 vector<int> v;
     65 set<int> ts;
     66 vector<int> ans;
     67 int main()
     68 {
     69     N = read(),M = read();
     70     init(N);
     71     int a,b;
     72     _for(i,0,M)
     73     {
     74         a = read(),b = read();
     75         G[a].pb(b);
     76         G[b].pb(a);
     77     }
     78     K = read();
     79     _for(i,0,K)
     80     {
     81         int t = read();
     82         v.pb(t);
     83         ts.insert(t);
     84     }
     85     
     86     _for(i,0,N)
     87         if(!ts.count(i))
     88         {
     89             cnt ++;
     90             _for(j,0,G[i].size())
     91                 if(!ts.count(G[i][j]))
     92                     unite(i,G[i][j]);
     93         }
     94     ans.pb(cnt);
     95     _rep(i,v.size()-1,-1)
     96     {
     97         cnt ++;
     98         _for(j,0,G[v[i]].size())
     99             if(!ts.count(G[v[i]][j]))
    100                 unite(v[i],G[v[i]][j]);
    101         ans.pb(cnt);
    102         auto p = ts.find(v[i]);
    103         ts.erase(p);
    104     }
    105     _rep(i,ans.size()-1,-1)
    106         printf("%d\n",ans[i]);
    107     return 0;
    108 }

转载于:https://www.cnblogs.com/Asurudo/p/11552372.html