P1197-[JSOI2008]星球大战


  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 }

优质内容筛选与推荐>>
1、数据库优化技巧之in和not in
2、Murano Deployment
3、mysql用merge合并表
4、PowerTip of the Day-Get Process Owners
5、值得细细品读的URL资源


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号