Guest User

Untitled

a guest
Feb 4th, 2018
770
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 200043;
  6.  
  7. set<int> g[N];
  8.  
  9. set<int> unused;
  10. int cc = 0;
  11. vector<int> comps;
  12.  
  13. void dfs(int x)
  14. {
  15. unused.erase(x);
  16. comps[cc]++;
  17. int cur = -1;
  18. while(true)
  19. {
  20. auto it = unused.upper_bound(cur);
  21. if (it == unused.end())
  22. break;
  23. cur = *it;
  24. if (g[x].count(cur))
  25. continue;
  26. dfs(cur);
  27. }
  28. }
  29.  
  30. int main()
  31. {
  32. int n, m;
  33. cin >> n >> m;
  34. for(int i = 0; i < m; i++)
  35. {
  36. int x, y;
  37. scanf("%d %d", &x, &y);
  38. --x;
  39. --y;
  40. g[x].insert(y);
  41. g[y].insert(x);
  42. }
  43. for(int i = 0; i < n; i++)
  44. unused.insert(i);
  45. for(int i = 0; i < n; i++)
  46. if (unused.count(i))
  47. {
  48. comps.push_back(0);
  49. dfs(i);
  50. cc++;
  51. }
  52. sort(comps.begin(), comps.end());
  53. printf("%d\n", cc);
  54. for(int i = 0; i < cc; i++)
  55. printf("%d ", comps[i]);
  56. return 0;
  57. }
RAW Paste Data