Advertisement
Guest User

Untitled

a guest
Nov 24th, 2014
162
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.16 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <tuple>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <map>
  10. #include <stack>
  11. #include <set>
  12. #include <bitset>
  13. #include <algorithm>
  14. #include <functional>
  15. #include <deque>
  16. #include <list>
  17.  
  18. #define INF 1000000000
  19. #define mod 1000000007
  20. #define PI 3.14159265358979323846
  21.  
  22. using namespace std;
  23.  
  24. int dsuParent[100005];
  25.  
  26. int dsuGetSet(int v)
  27. {
  28. if(dsuParent[v] == v)
  29. return v;
  30. return dsuParent[v] = dsuGetSet(dsuParent[v]);
  31. }
  32.  
  33. void dsuMergeSet(int u, int v)
  34. {
  35. u = dsuGetSet(u);
  36. v = dsuGetSet(v);
  37. if(u != v)
  38. dsuParent[u] = v;
  39. }
  40.  
  41. struct Edge
  42. {
  43. Edge () : u(0), v(0) {}
  44. Edge(int u, int v) : u(u), v(v) {}
  45. int u, v;
  46. } edges[100005];
  47.  
  48. int order[100005];
  49. int ans[100005];
  50. bool used[100005];
  51.  
  52. int main()
  53. {
  54.  
  55. #ifndef ONLINE_JUDGE
  56. freopen("input.txt", "r", stdin);
  57. //freopen("output.txt", "w", stdout);
  58. #endif
  59.  
  60. int n, m;
  61. scanf("%d%d", &n, &m);
  62.  
  63. for(int i = 0; i < n; i++)
  64. {
  65. dsuParent[i] = i;
  66. }
  67.  
  68. for(int i = 0; i < m; i++)
  69. {
  70. scanf("%d%d", &edges[i].u, &edges[i].v);
  71. edges[i].u--, edges[i].v--;
  72. }
  73. int q;
  74. scanf("%d", &q);
  75.  
  76. for(int i = 0; i < q; i++)
  77. {
  78. scanf("%d", &order[i]);
  79. order[i]--;
  80. used[order[i]] = true;
  81. }
  82.  
  83. int r = n;
  84.  
  85.  
  86. for(int i = 0; i < m; i++)
  87. {
  88. if(!used[i])
  89. {
  90. int u, v, a, b;
  91. u = edges[order[i]].u;
  92. v = edges[order[i]].v;
  93. a = dsuGetSet(u);
  94. b = dsuGetSet(v);
  95. if(a != b)
  96. {
  97. dsuMergeSet(edges[i].u, edges[i].v);
  98. r--;
  99. }
  100. }
  101. }
  102.  
  103. for(int i = q - 1; i >= 0; i--)
  104. {
  105. ans[i] = r;
  106. int u, v, a, b;
  107. u = edges[order[i]].u;
  108. v = edges[order[i]].v;
  109. a = dsuGetSet(u);
  110. b = dsuGetSet(v);
  111. if(a != b)
  112. {
  113. r--;
  114. dsuMergeSet(a, b);
  115. }
  116. }
  117.  
  118. for(int i = 0; i < q; i++)
  119. {
  120. printf("%d ", ans[i]);
  121. }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement