Advertisement
Guest User

Untitled

a guest
Jan 22nd, 2020
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define s second
  3. #define f first
  4. #define ALL(v) v.begin(), v.end()
  5. using namespace std;
  6. const int N = 2e5 + 5;
  7. int q, m, x, y, g[N], otv, n, k[N], par[N], ran[N], parent[N];
  8. void make_set( int v ){
  9.     parent[v] = v;
  10.     ran[v] = 0;
  11. }
  12. int find_set( int v ){
  13.     if( v == parent[v] )
  14.         return v;
  15.     return parent[v] = find_set(parent[v]);
  16. }
  17. bool union_set( int a, int b ){
  18.     a = find_set(a);
  19.     b = find_set(b);
  20.     if( a != b ){
  21.         if( ran[a] < ran[b] )
  22.             swap(a,b);
  23.         parent[b] = a;
  24.         if( ran[a] == ran[b] )
  25.             ran[a]++;
  26.         return 1;
  27.     }
  28.     else
  29.         return 0;
  30. }
  31. vector <pair<int,int>> paths;
  32. vector <int> obhod, ans;
  33. int main()
  34. {
  35.     ios_base::sync_with_stdio(0);
  36.     freopen( "input.txt", "r", stdin );
  37.     cin >> n >> m;
  38.     for( int i = 1; i <= n; i++ )
  39.         make_set(i);
  40.     for( int i = 0; i < m; i++ ){
  41.         g[i]++;
  42.         cin >> x >> y;
  43.         paths.push_back( {x, y} );
  44.     }
  45.     cin >> q;
  46.     for( int i = 0; i < q; i++ ){
  47.         cin >> x;
  48.         obhod.push_back(x-1);
  49.         g[x-1]--;
  50.     }
  51.     for( int i = 0; i < m; i++ ){
  52.         if( g[i] ){
  53.             union_set( paths[i].f, paths[i].s );
  54.         }
  55.     }
  56.     for( int i = 1; i <= n; i++ ){
  57.         if( find_set(i) == i )
  58.             otv++;
  59.     }
  60.     for( auto i : obhod ){
  61.         ans.push_back(otv);
  62.         if( union_set( paths[i].f, paths[i].s ) )
  63.             otv--;
  64.     }
  65.     reverse( ALL(ans) );
  66.     for( auto i : ans )
  67.         cout << i << ' ';
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement