fork download
copy 
  1. #include <algorithm>
  2. #include <ctime>
  3. #include <cmath>
  4. #include <string>
  5. #include <memory>
  6. #include <cstdio>
  7. #include <climits>
  8. #include <cstring>
  9. #include <cstdlib>
  10. #include <iostream>
  11.  
  12. using namespace std;
  13.  
  14. const int maxn = 100000 + 5;
  15. const int maxm = 2000000 + 5;
  16.  
  17. typedef unsigned int uint;
  18. typedef long long int64;
  19. typedef unsigned long long uint64;
  20.  
  21. template <class T> inline T Sqr(const T & x) { return x * x; }
  22. template <class T> inline T Abs(const T & x) { return x > 0 ? x : -x; }
  23. template <class T> inline T Min(const T & a, const T & b) { return a < b ? a : b; }
  24. template <class T> inline T Max(const T & a, const T & b) { return a > b ? a : b; }
  25. template <class T> inline T Ksm(const T & a, const T & b, const T & m) { T _ = 1; for (; b; b >>= 1, a = a * a % m) (b & 1) ? _ = _ * a % m : 0; return _ % m; }
  26. template <class T> inline void Swap(T & a, T & b) { T _; _ = a; a = b; b = _; }
  27.  
  28. typedef int pint[maxn * 2];
  29. typedef int eint[maxm * 2];
  30.  
  31. int n, m, e(1), ans, num[maxm], dfn;
  32. pint edge, vp, vps, pre, suc, aps;
  33. eint next, point, s;
  34.  
  35. inline void link(int u, int v)
  36. {
  37.    point[++e] = v; next[e] = edge[u]; edge[u] = e;
  38.    point[++e] = u; next[e] = edge[v]; edge[v] = e;
  39. }
  40.  
  41. inline int getint()
  42. {
  43.    char ch = getchar(); int result = 0;
  44.    for (; '0' > ch || ch > '9'; ch = getchar());
  45.    for (; '0' <= ch && ch <= '9'; )
  46.       result = result * 10 + ch - '0', ch = getchar();
  47.    return result;
  48. }
  49.  
  50. void init()
  51. {
  52.    n = getint(), m = getint();
  53.    for (int i = 1, u, v; i <= m; ++i)
  54.       link(u = getint(), v = getint());
  55.    for (int i = 0; i <= n; ++i)
  56.       pre[i] = i - 1, suc[i] = i + 1;
  57.    pre[0] = n, suc[n] = 0;
  58. }
  59.  
  60. void bfs()
  61. {
  62.    int l, r, res;
  63.    for (l = r = res = 1, s[l] = suc[0]; l <= r; ++l)
  64.    {
  65.       aps[s[l]] = 1, vp[s[l]] = ++dfn, pre[suc[s[l]]] = pre[s[l]], suc[pre[s[l]]] = suc[s[l]];
  66.       for (int i = edge[s[l]]; i; i = next[i]) vp[point[i]] = dfn;
  67.       for (int i = suc[0]; i; i = suc[i])
  68.          if (!aps[i] && vp[i] != dfn)
  69.          {
  70.             s[++r] = i, aps[i] = 1;
  71.             pre[suc[i]] = pre[i], suc[pre[i]] = suc[i];
  72.             if (!vps[i]) ++res, vps[i] = 1;
  73.          }
  74.    }
  75.    num[ans + 1] = res;
  76. }
  77.  
  78. void newgraph()
  79. {
  80.    for (; suc[0]; bfs(), ++ans);
  81.    sort(num + 1, num + ans + 1);
  82.    printf("%d\n", ans);
  83.    for (int i = 1; i <= ans; ++i) 
  84.       printf("%d ", num[i]);
  85. }
  86.  
  87. int main()
  88. {
  89.    init();
  90.    newgraph();
  91.    return 0;
  92. }
Success #stdin #stdout 0.01s 62056KB
comments (?)
stdin
copy 
7 16
1 3
1 4
1 5
2 3
3 4
4 5
4 7
4 6
5 6
6 7
2 4
2 7
2 5
3 5
3 7
1 7
stdout
copy 
3
1 2 4
https://ideone.com/sj4k5O
language:
C++ (gcc 8.3)
created:
11 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!