fork download
copy 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 456789
  13. #define MAX 1037471823
  14. #define Q 103
  15.  
  16. using namespace std;
  17.  
  18. struct node
  19. {
  20. 	int x, y;
  21. 	bool operator < (const node &k) const { return x < k.x; }
  22. } c[MS];
  23. int n, m, h[MS], l[MS], now, a, b, ans[MS], k[MS], q;
  24. bool r[MS];
  25.  
  26. int Head(int x)
  27. {
  28. 	while (h[x] != h[h[x]]) h[x] = h[h[x]];
  29. 	return h[x];
  30. }
  31.  
  32. int main()
  33. {
  34. 	scanf("%d%d", &n, &m);
  35. 	rep(i, 1, n) h[i] = i; now = n;
  36. 	rep(i, 1, m) scanf("%d%d", &c[i].x, &c[i].y);
  37. 	rep(i, 1, m) c[i].x++, c[i].y++;
  38. 	rep(i, 1, m) c[i+m].x = c[i].y, c[i+m].y = c[i].x; m *= 2;
  39. 	sort(c+1, c+1+m); c[m+1].x = MAX;
  40. 	k[1] = 1; rep(i, 2, n+1) { k[i] = k[i-1]; while (c[k[i]].x < i) k[i]++; }
  41. 	scanf("%d", &q); rep(i, 1, q) scanf("%d", &l[i]); rep(i, 1, q) l[i]++;
  42. 	rep(i, 1, n) r[i] = true; rep(i, 1, q) r[l[i]] = false;
  43. 	rep(i, 1, m) if (r[c[i].x] && r[c[i].y])
  44. 	{
  45. 		a = Head(c[i].x); b = Head(c[i].y);
  46. 		if (a != b) now--, h[a] = b;
  47. 	}
  48. 	down(o, q, 1)
  49. 	{
  50. 		ans[o] = now-o;
  51. 		r[l[o]] = true;
  52. 		rep(i, k[l[o]], k[l[o]+1]-1) if (r[c[i].x] && r[c[i].y])
  53. 		{
  54. 			a = Head(c[i].x); b = Head(c[i].y);
  55. 			if (a != b) now--, h[a] = b;
  56. 		}
  57. 	}
  58. 	printf("%d\n", now);
  59. 	rep(i, 1, q) printf("%d\n", ans[i]);
  60. 	return 0;
  61. }
  62.  
Success #stdin #stdout 0s 14456KB
comments (?)
stdin
copy 
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
stdout
copy 
1
1
1
2
3
3
https://ideone.com/b3c69x
BZOJ 1015
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!