Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define in_arr(n,A) for(int i=0;i<n;i++)cin>>A[i];
- #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #define vi vector <int>
- #define vl vector <ll>
- #define out_arr(n,A) for(int i=0;i<n;i++)cout<<A[i]<<" ";
- #define LINE cout << endl
- #define SPACE cout << " "
- #define pb push_back
- #define FF first
- #define SS second
- #define YES cout << "YES"
- #define NO cout << "NO"
- #define wrong cout << -1
- #define pll pair <ll, ll>
- #define pii pair <int, int>
- #define OO INT_MAX
- #define SMALL INT_MIN
- #define BIGx2 LONG_LONG_MAX
- #define sz size()
- //BIT_OP
- #define isOn(s, j) (s & (1<<j))
- #define setBit(s, j) (s |= ( 1<< j))
- #define clearBit(s, j) (s &= ~( 1 << j ))
- #define lowBit(s) (s & (-s))
- #define setAll(s, n) ( s = ( 1 << n ) - 1)
- #define modulo(s, n) ((s) & ( n - 1 ))
- #define isPowerOfTwo(s) (!(s & (s - 1)))
- #define nearestPowerOfTwo(s) ((int)pow(2.0, (int)((log((double)s) / log(2.0)) + 50. )))
- #define nextnearestPowerOfTwo(s) (1<<(32 - __builtin_clz(s)))
- #define turnoffLastBit(s) ((s) & (s - 1))
- #define turnonLastZero(s) ((S) | (s + 1))
- #define turnoffLastConsecutiveBits(s) ((s) & (s + 1))
- typedef long long ll;
- using namespace std;
- int n, m, cnt;
- pair <int, int> A[200200];
- int B[200200];
- int parent[200200];
- vector <int> v;
- int getPA(int t)
- {
- if(parent[t] == t)
- return t;
- else
- return parent[t] = getPA(parent[t]);
- }
- int main()
- {
- IOS
- cin >> n >> m;
- cnt = n;
- for(int i = 0 ; i < 200200 ; i++)
- parent[i] = i;
- for(int i = 0 ; i < m ; i++)
- {
- int t, tt;
- cin >> t >> tt;
- A[i].FF = t;
- A[i].SS = tt;
- }
- for(int i = 0 ; i < m ; i++)
- cin >> B[i];
- reverse(B, B + m);
- for(int i = 0 ; i < m ; i++)
- {
- v.pb(cnt);
- if(getPA(A[B[i] - 1].SS) != getPA(A[B[i] - 1].FF))
- {
- cnt--;
- parent[A[B[i] - 1].FF] = A[B[i] - 1].SS;
- }
- }
- reverse(v.begin(), v.end());
- for(int i = 0 ; i < v.sz ; i++)
- {
- cout << v[i];
- LINE;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement