Advertisement
Dzham

Untitled

Apr 15th, 2018
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.03 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. int size_g;
  12. std::vector<std::vector<bool>> data;
  13. std::vector<int> used;
  14.  
  15. public:
  16. std::vector<bool> isused;
  17.  
  18. Graph() {
  19. }
  20.  
  21. explicit Graph(int n) {
  22. data.resize(n);
  23. size_g = n;
  24. for (int i = 0; i < n; i++) {
  25. data[i].resize(n);
  26. }
  27. isused.resize(n);
  28. }
  29.  
  30. void insert(int a, int b) {
  31. data[a - 1][b - 1] = true;
  32. data[b - 1][a - 1] = true;
  33. }
  34.  
  35. void subgraph2(int a) {
  36. if (!isused[a - 1]) {
  37. isused[a - 1] = true;
  38. used.push_back(a);
  39. for (int i = 0; i < size_g; i++) {
  40. if (data[a - 1][i]) {
  41. subgraph2(i + 1);
  42. }
  43. }
  44. }
  45. }
  46.  
  47. std::vector<int> subgraph(int a) {
  48. used = {};
  49. subgraph2(a);
  50. return used;
  51. }
  52. };
  53.  
  54. int main() {
  55. int N, M;
  56. int a, b;
  57. std::cin >> N >> M;
  58. if (N != 0 && M != 0) {
  59. Graph graph(N);
  60. for (int i = 0; i < M; i++) {
  61. std::cin >> a >> b;
  62. graph.insert(a, b);
  63. }
  64. std::vector<std::vector<int>> result;
  65. for (int i = 0; i < N; i++) {
  66. if (!graph.isused[i]) {
  67. result.push_back(graph.subgraph(i + 1));
  68. }
  69. }
  70. std::cout << result.size() << '\n';
  71. for (int i = 0; i < result.size(); i++) {
  72. std::cout << result[i].size() << '\n';
  73. std::cout << result[i][0];
  74. for (int j = 1; j < result[i].size(); j++) {
  75. std::cout << " " << result[i][j];
  76. }
  77. std::cout << '\n';
  78. }
  79. } else if (N == 0) {
  80. std::cout << 0;
  81. } else {
  82. std::cout << N << '\n';
  83. for (int i = 0; i < N; i++) {
  84. std::cout << 1 << '\n' << i + 1 << '\n';
  85. }
  86. }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement