fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5.  
  6. long long n,m,q;
  7. pair<long long,long long> pr[MaxN],query[MaxN];
  8. bool del[MaxN];
  9.  
  10. struct DSU
  11. {
  12.     long long lab[MaxN];
  13.  
  14.     void init()
  15.     {
  16.         for (long long i=1;i<=n;i++)
  17.         {
  18.             lab[i]=-1;
  19.         }
  20.     }
  21.  
  22.     long long get_root(long long u)
  23.     {
  24.         if(lab[u]<0) return u;
  25.         return lab[u]=get_root(lab[u]);
  26.     }
  27.  
  28.     void unite(long long u,long long v)
  29.     {
  30.         long long x=get_root(u),y=get_root(v);
  31.  
  32.         if(x==y) return;
  33.  
  34.         if(lab[x]>lab[y]) swap(x,y);
  35.  
  36.         lab[x]+=lab[y];
  37.         lab[y]=x;
  38.     }
  39.  
  40.     bool check(long long u,long long v)
  41.     {
  42.         return get_root(u)==get_root(v);
  43.     }
  44.  
  45.     long long get_size(long long u)
  46.     {
  47.         return -lab[get_root(u)];
  48.     }
  49. };
  50.  
  51. DSU dsu;
  52.  
  53. void input()
  54. {
  55.     cin>>n>>m>>q;
  56.  
  57.     for(long long i=1;i<=m;i++)
  58.     {
  59.         cin>>pr[i].first>>pr[i].second;
  60.     }
  61.  
  62.     for(long long i=1;i<=q;i++)
  63.     {
  64.         cin>>query[i].first>>query[i].second;
  65.  
  66.         del[query[i].first]=true;
  67.     }
  68. }
  69.  
  70. void solve()
  71. {
  72.     dsu.init();
  73.  
  74.     for(long long i=1;i<=m;i++)
  75.     {
  76.         if(del[i]==false)
  77.         {
  78.             dsu.unite(pr[i].first,pr[i].second);
  79.         }
  80.     }
  81.  
  82.     vector<long long> ans;
  83.  
  84.     for(long long i=q;i>=1;i--)
  85.     {
  86.         long long e=query[i].first;
  87.         long long c=query[i].second;
  88.  
  89.         ans.push_back(dsu.get_size(c));
  90.         dsu.unite(pr[e].first,pr[e].second);
  91.     }
  92.  
  93.     reverse(ans.begin(),ans.end());
  94.  
  95.     for(long long x:ans)
  96.     {
  97.         cout<<x<<"\n";
  98.     }
  99. }
  100.  
  101. int main()
  102. {
  103.     ios_base::sync_with_stdio(0);
  104.     cin.tie(0);
  105.  
  106.     input();
  107.     solve();
  108. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z0liDq
language:
C++14 (gcc 8.3)
created:
2 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!