Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define s second
- #define f first
- #define ALL(v) v.begin(), v.end()
- using namespace std;
- const int N = 2e5 + 5;
- int q, m, x, y, g[N], otv, n, k[N], par[N], ran[N], parent[N];
- void make_set( int v ){
- parent[v] = v;
- ran[v] = 0;
- }
- int find_set( int v ){
- if( v == parent[v] )
- return v;
- return parent[v] = find_set(parent[v]);
- }
- bool union_set( int a, int b ){
- a = find_set(a);
- b = find_set(b);
- if( a != b ){
- if( ran[a] < ran[b] )
- swap(a,b);
- parent[b] = a;
- if( ran[a] == ran[b] )
- ran[a]++;
- return 1;
- }
- else
- return 0;
- }
- vector <pair<int,int>> paths;
- vector <int> obhod, ans;
- int main()
- {
- ios_base::sync_with_stdio(0);
- freopen( "input.txt", "r", stdin );
- cin >> n >> m;
- for( int i = 1; i <= n; i++ )
- make_set(i);
- for( int i = 0; i < m; i++ ){
- g[i]++;
- cin >> x >> y;
- paths.push_back( {x, y} );
- }
- cin >> q;
- for( int i = 0; i < q; i++ ){
- cin >> x;
- obhod.push_back(x-1);
- g[x-1]--;
- }
- for( int i = 0; i < m; i++ ){
- if( g[i] ){
- union_set( paths[i].f, paths[i].s );
- }
- }
- for( int i = 1; i <= n; i++ ){
- if( find_set(i) == i )
- otv++;
- }
- for( auto i : obhod ){
- ans.push_back(otv);
- if( union_set( paths[i].f, paths[i].s ) )
- otv--;
- }
- reverse( ALL(ans) );
- for( auto i : ans )
- cout << i << ' ';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement