fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int MAXN = 1e5 + 15;
  6.  
  7. struct DATA {
  8.     int u, v;
  9. };
  10.  
  11. int N, M, Q;
  12. DATA A[MAXN];
  13. int B[MAXN];
  14. bool vis[MAXN];
  15.  
  16. struct Dosu {
  17.     int par[MAXN], sz[MAXN];
  18.     void INIT() {
  19.         for (int i = 1; i <= MAXN - 1; i++) par[i] = i, sz[i] = 1;
  20.     }
  21.  
  22.     int find_set(int u) {
  23.         return (par[u] == u ? u : par[u] = find_set(par[u]));
  24.     }
  25.  
  26.     bool union_set(int u, int v) {
  27.         int x = find_set(u), y = find_set(v);
  28.         if (x != y) {
  29.             par[x] = y;
  30.             return true;
  31.         }
  32.         return false;
  33.     }
  34. } DSU;
  35.  
  36.  
  37. main() {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0);
  40.     cout.tie(0);
  41.  
  42.     cin >> N >> M >> Q;
  43.     DSU.INIT();
  44.     for (int i = 1; i <= M; i++) cin >> A[i].u >> A[i].v;
  45.     for (int i = 1; i <= Q; i++) {
  46.         cin >> B[i];
  47.         vis[B[i]] = true;
  48.     }
  49.     for (int i = 1; i <= M; i++) if (!vis[i]) {
  50.         DSU.union_set(A[i].u, A[i].v);
  51.     }
  52.  
  53.     int cnt = 0;
  54.     for (int i = 1; i <= N; i++) if (DSU.par[i] == i) cnt++;
  55.     vector<int> kq;
  56.     for (int i = Q; i >= 1; i--) {
  57.         kq.push_back(cnt);
  58.         cnt -= DSU.union_set(A[B[i]].u, A[B[i]].v);
  59.     }
  60.     reverse(kq.begin(), kq.end());
  61.     for (auto v : kq) cout << v << '\n';
  62. }
  63.  
Success #stdin #stdout 0.01s 6016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MZ0cb8
language:
C++ (gcc 8.3)
created:
30 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!