fork download
copy 
  1. /*Code by HsonW, 11/2 NH-Hue. Just a newbie <3*/
  2. /*#CuoiVOIdanhbaiquochochue*/
  3. /*nguyenngockhanhthi<3*/
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. using int64=long long;
  7. #define ll long long
  8. const int MOD=1e9+7;
  9. const int MAX=1e5+100;
  10. typedef pair<int,int> ii;
  11. #define ull unsigned long long
  12. #define i128 __int128
  13. struct DSU{
  14.     vector<int>sz,par;
  15.     DSU (int n){
  16.         sz.resize(n+5);
  17.         par.resize(n+5);
  18.         for(int i=1;i<=n;i++){
  19.             sz[i]=1;
  20.             par[i]=i;
  21.         }
  22.     }
  23.     int find(int u){
  24.         if(par[u]==u) return u;
  25.         else return par[u]=find(par[u]);
  26.     }
  27.     bool check(int u,int v){
  28.         u=find(u);
  29.         v=find(v);
  30.         if(u==v) return false;
  31.         if(sz[u]<sz[v])  swap(u,v);
  32.         sz[u]+=sz[v];
  33.         par[v]=u;
  34.         return true;
  35.     }
  36. };
  37. bool dmg[MAX];
  38. signed main(){
  39.     #define name "hsonw"
  40.     ios::sync_with_stdio(0);
  41.     cin.tie(NULL);
  42.     if(fopen(name ".inp", "r")){
  43.         freopen(name ".inp", "r", stdin);
  44.         freopen(name ".out", "w", stdout);
  45.     }
  46.     int n,m,q;
  47.     cin >>n>>m>>q;
  48.     vector<ii>v(m+1);
  49.     vector<int>Q(q+1);
  50.     DSU dsu(n);
  51.     for(int i=1;i<=m;i++){
  52.         int a,b;
  53.         cin >>v[i].first>>v[i].second;
  54.  
  55.     }
  56.     for(int i=1;i<=q;i++){
  57.         int t;
  58.         cin >>t;
  59.         dmg[t]=true;
  60.         Q[i]=t;
  61.     }
  62.     int kthi=n;
  63.     for(int i=1;i<=m;i++){
  64.         if(!dmg[i]){
  65.             if(dsu.check(v[i].first,v[i].second)) kthi--;
  66.         }
  67.     }
  68.     vector<int>ans(q+1);
  69.     for(int i=q;i>0;i--){
  70.         ans[i]=kthi;
  71.         int a=v[Q[i]].first;
  72.         int b=v[Q[i]].second;
  73.         if(dsu.check(a,b)) kthi--;
  74.     }
  75.     for(int i=1;i<=q;i++) cout <<ans[i]<<"\n";
  76.  
  77.  
  78. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 4 3
1 2
2 3
1 3
3 4
2
4
3
stdout
copy 
1
2
3
https://ideone.com/705mSb
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!