Advertisement
Guest User

Untitled

a guest
Feb 19th, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. bool mark[100000] = {};
  6. int dfs(int s, vector<vector<long long> >& v , vector<long long>& res) {
  7. int cnt = 1;
  8. mark[s] = 1;
  9. for (int i = 0 ; i < v[s].size(); ++i) {
  10. if (mark[v[s][i]] != 1) {
  11. cnt += dfs(v[s][i], v, res);
  12. res.push_back(v[s][i]);
  13. }
  14. }
  15. return cnt;
  16. }
  17.  
  18. int main () {
  19. int n, m;
  20. cin >> n >> m;
  21. vector <vector < long long > > v(n);
  22. vector <vector < long long > > res;
  23.  
  24. for (int i = 0 ; i < m ; ++i) {
  25. int a, b;
  26. cin >> a >> b;
  27. v[a - 1].push_back(b - 1);
  28. v[b - 1].push_back(a - 1);
  29. }
  30. for (int i = 0; i < n; ++i) {
  31. if (mark[i]) continue;
  32. vector<long long > tmp;
  33. tmp.push_back(i);
  34. dfs(i, v, tmp);
  35. res.push_back(tmp);
  36. }
  37.  
  38. cout << res.size() << "\n" ;
  39. for (int i = 0; i < res.size(); ++i) {
  40. cout << res[i].size() << "\n";
  41. for (int j = 0; j < res[i].size(); ++j) {
  42. cout << res[i][j] + 1 << " ";
  43. }
  44. cout << "\n";
  45. }
  46. return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement