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 123456
  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, d[MS], l[MS], h[MS], ys, k[MS], m, s[MS], a, v[MS], vv;
  24. bool b[MS];
  25.  
  26. void DFS(int x)
  27. {
  28. 	v[++vv] = x; d[x] = vv; l[x] = vv;
  29. 	rep(i, k[x], k[x+1]-1)
  30. 	{
  31. 		 if (d[c[i].y] == 0) DFS(c[i].y); 
  32. 		 l[x] = min(l[x], l[c[i].y]);
  33. 	}
  34. 	if (d[x] == l[x])
  35. 	{
  36. 		ys++;
  37. 		rep(i, d[x], vv) h[v[i]] = ys;
  38. 		s[ys] = vv-d[x]+1;
  39. 		vv = d[x]-1;
  40. 	}
  41. }
  42.  
  43. int main()
  44. {
  45. 	scanf("%d%d", &n, &m);
  46. 	rep(i, 1, m) scanf("%d%d", &c[i].x, &c[i].y);
  47. 	sort(c+1, c+1+m); c[m+1].x = MAX;
  48. 	k[1] = 1; rep(i, 2, n+1) { k[i] = k[i-1]; while (c[k[i]].x < i) k[i]++; }
  49. 	rep(i, 1, n) l[i] = MAX;
  50. 	rep(i, 1, n) if (h[i] == 0) DFS(i);
  51. 	rep(i, 1, ys) b[i] = true;
  52. 	rep(i, 1, m) if (h[c[i].x] != h[c[i].y]) b[h[c[i].x]] = false;
  53. 	a = 0; rep(i, 1, ys) if (b[i]) a++;
  54. 	if (a != 1) printf("0\n"); else
  55. 		rep(i, 1, ys) if (b[i]) printf("%d\n", s[i]);
  56. 	return 0;
  57. }
  58.  
Success #stdin #stdout 0s 7324KB
comments (?)
stdin
copy 
3 3
1 2
2 1
2 3
stdout
copy 
1
https://ideone.com/DV1CCb
BZOJ 1051
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!