Advertisement
Dzham

Untitled

Apr 14th, 2018
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iterator>
  5. #include <unordered_map>
  6. #include <unordered_set>
  7. #include <string>
  8.  
  9. class Graph {
  10. private:
  11. std::unordered_map<int, std::vector<int>> edges;
  12. std::unordered_set<int> used;
  13. std::unordered_set<int> notused;
  14.  
  15. public:
  16. Graph() {
  17. }
  18.  
  19. explicit Graph(int n) {
  20. for (int i = 0; i < n; i++) {
  21. edges[i + 1] = {};
  22. notused.insert(i + 1);
  23. }
  24. }
  25.  
  26. std::unordered_set<int> vertexes() {
  27. std::unordered_set<int> res;
  28. for (auto i : edges) {
  29. res.insert(i.first);
  30. }
  31. return res;
  32. }
  33.  
  34. void insert(int a, int b) {
  35. edges[a].push_back(b);
  36. edges[b].push_back(a);
  37. notused.insert(a);
  38. notused.insert(b);
  39. }
  40.  
  41. void subgraph2(int a) {
  42. if (used.find(a) == used.end()) {
  43. used.insert(a);
  44. notused.erase(a);
  45. for (auto i : edges[a]) {
  46. subgraph2(i);
  47. }
  48. }
  49. }
  50.  
  51. std::unordered_set<int> subgraph(int a) {
  52. used.clear();
  53. subgraph2(a);
  54. return used;
  55. }
  56.  
  57. std::unordered_set<int> notuseds() {
  58. return notused;
  59. }
  60. };
  61.  
  62. int main() {
  63. int N, M;
  64. int a, b;
  65. std::cin >> N >> M;
  66. if (N != 0 && M != 0) {
  67. Graph graph(N);
  68. for (int i = 0; i < M; i++) {
  69. std::cin >> a >> b;
  70. graph.insert(a, b);
  71. }
  72. std::unordered_set<int> vertexes;
  73. vertexes = graph.notuseds();
  74. int number = 0;
  75. std::vector<std::unordered_set<int>> result;
  76. std::unordered_set<int> preresult;
  77. std::unordered_set<int> difference;
  78. while (vertexes.size() != 0) {
  79. preresult = graph.subgraph(*vertexes.begin());
  80. result.push_back(preresult);
  81. vertexes = graph.notuseds();
  82. number++;
  83. }
  84. std::cout << number << '\n';
  85. for (int i = 0; i < number; i++) {
  86. std::cout << result[i].size() << '\n';
  87. std::cout << *result[i].begin();
  88. auto beg = result[i].begin();
  89. beg++;
  90. while (beg != result[i].end()) {
  91. std::cout << " " << *beg++;
  92. }
  93. std::cout << '\n';
  94. }
  95. } else if (N == 0) {
  96. std::cout << 0;
  97. } else {
  98. std::cout << N << '\n';
  99. for (int i = 0; i < N; i++) {
  100. std::cout << 1 << '\n' << i + 1 << '\n';
  101. }
  102. }
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement