fork(2) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<functional>
  5. #include<math.h>
  6. #include<assert.h>
  7. #include<stdarg.h>
  8. #include<time.h>
  9. #include<limits.h>
  10. #include<ctype.h>
  11. #include<string>
  12. #include<map>
  13. #include<set>
  14. #include<queue>
  15. #include<algorithm>
  16. #include<vector>
  17. #include<iostream>
  18. #include<sstream>
  19. using namespace std;
  20.  
  21. int n, m, k, x, y, h[100005], e[1000005][2], ew, g[100005], q[100005], qr, qw;
  22. bool b[100005];
  23.  
  24. void adde(int x, int y) {
  25. e[ew][0] = y;
  26. e[ew][1] = h[x];
  27. h[x] = ew++;
  28. g[x]++;
  29. }
  30.  
  31. int main() {
  32. scanf("%d%d%d", &n, &m, &k);
  33. memset(h, -1, sizeof(h));
  34. ew = 0;
  35. memset(g, 0, sizeof(g));
  36. while (m--) {
  37. scanf("%d%d", &x, &y);
  38. adde(x, y);
  39. adde(y, x);
  40. }
  41. memset(b, true, sizeof(b));
  42. qr = qw = 0;
  43. for (int i = 0; i < n; ++i) {
  44. if (g[i] < k) {
  45. q[qw++] = i;
  46. b[i] = false;
  47. }
  48. }
  49. while (qr != qw) {
  50. x = q[qr++];
  51. for (int i = h[x]; i != -1; i = e[i][1]) {
  52. y = e[i][0];
  53. if (b[y]) {
  54. g[y]--;
  55. if (g[y] < k) {
  56. q[qw++] = y;
  57. b[y] = false;
  58. }
  59. }
  60. }
  61. }
  62. printf("%d\n", n - qw);
  63. return 0;
  64. }
Success #stdin #stdout 0s 11984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/UqNfqF
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!