Advertisement
Guest User

Untitled

a guest
May 21st, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define in_arr(n,A) for(int i=0;i<n;i++)cin>>A[i];
  3. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define vi vector <int>
  5. #define vl vector <ll>
  6. #define out_arr(n,A) for(int i=0;i<n;i++)cout<<A[i]<<" ";
  7. #define LINE cout << endl
  8. #define SPACE cout << " "
  9. #define pb push_back
  10. #define FF first
  11. #define SS second
  12. #define YES cout << "YES"
  13. #define NO cout << "NO"
  14. #define wrong cout << -1
  15. #define pll pair <ll, ll>
  16. #define pii pair <int, int>
  17. #define OO INT_MAX
  18. #define SMALL INT_MIN
  19. #define BIGx2 LONG_LONG_MAX
  20. #define sz size()
  21. //BIT_OP
  22. #define isOn(s, j) (s & (1<<j))
  23. #define setBit(s, j) (s |= ( 1<< j))
  24. #define clearBit(s, j) (s &= ~( 1 << j ))
  25. #define lowBit(s) (s & (-s))
  26. #define setAll(s, n) ( s = ( 1 << n ) - 1)
  27. #define modulo(s, n) ((s) & ( n - 1 ))
  28. #define isPowerOfTwo(s) (!(s & (s - 1)))
  29. #define nearestPowerOfTwo(s) ((int)pow(2.0, (int)((log((double)s) / log(2.0)) + 50. )))
  30. #define nextnearestPowerOfTwo(s) (1<<(32 - __builtin_clz(s)))
  31. #define turnoffLastBit(s) ((s) & (s - 1))
  32. #define turnonLastZero(s) ((S) | (s + 1))
  33. #define turnoffLastConsecutiveBits(s) ((s) & (s + 1))
  34. typedef long long ll;
  35. using namespace std;
  36. int n, m, cnt;
  37. pair <int, int> A[200200];
  38. int B[200200];
  39. int parent[200200];
  40. vector <int> v;
  41. int getPA(int t)
  42. {
  43. if(parent[t] == t)
  44. return t;
  45. else
  46. return parent[t] = getPA(parent[t]);
  47. }
  48. int main()
  49. {
  50. IOS
  51. cin >> n >> m;
  52. cnt = n;
  53. for(int i = 0 ; i < 200200 ; i++)
  54. parent[i] = i;
  55. for(int i = 0 ; i < m ; i++)
  56. {
  57. int t, tt;
  58. cin >> t >> tt;
  59. A[i].FF = t;
  60. A[i].SS = tt;
  61. }
  62.  
  63. for(int i = 0 ; i < m ; i++)
  64. cin >> B[i];
  65. reverse(B, B + m);
  66. for(int i = 0 ; i < m ; i++)
  67. {
  68. v.pb(cnt);
  69. if(getPA(A[B[i] - 1].SS) != getPA(A[B[i] - 1].FF))
  70. {
  71. cnt--;
  72. parent[A[B[i] - 1].FF] = A[B[i] - 1].SS;
  73. }
  74. }
  75. reverse(v.begin(), v.end());
  76. for(int i = 0 ; i < v.sz ; i++)
  77. {
  78. cout << v[i];
  79. LINE;
  80. }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement