Advertisement
achulkov2

Untitled

Apr 15th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int N;
  5. vector<vector<int>>g;
  6. vector <bool>visited(false);
  7. int ss = 0;
  8. vector<int>color;
  9. vector<int>klv;
  10. vector<vector<int>>nv;
  11. void DFS(int V)
  12. {
  13. visited[V] = true;
  14. color[V] = ss;
  15. nv[ss].push_back(V);
  16. for (int i = 0; i < g[V].size(); i++)
  17. {
  18. int to = g[V][i];
  19. if (!visited[to])
  20. {
  21. DFS(to);
  22. }
  23. }
  24. }
  25. int main()
  26. {
  27. int M, a, b,q;
  28. cin >> N >> M;
  29. g.resize(N);
  30. nv.resize(N);
  31. visited.resize(N);
  32. for (int i = 0; i < M; i++)
  33. {
  34. cin >> a >> b;
  35. a--;
  36. b--;
  37. g[a].push_back(b);
  38. g[b].push_back(a);
  39. }
  40. color.resize(N);
  41. for (int i = 0; i < N; i++)
  42. {
  43. if (!visited[i])
  44. {
  45. ss++;
  46. DFS(i);
  47. }
  48. }
  49. cout << ss;
  50. for (int i = 1; i <= ss; i++)
  51. {
  52. cout << endl << nv[i].size() << endl;
  53. q = nv[i].size();
  54. while (q > 0)
  55. {
  56. cout << nv[i][q - 1] + 1 << " ";
  57. q--;
  58. }
  59. }
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement