Advertisement
AlexGo11

Untitled

Jan 2nd, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.86 KB | None | 0 0
  1. //Основы теории графов и dfs. Теория. Задача E.
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. int n, m;
  5. vector < vector < int > > g;
  6. vector < bool > used;
  7. vector < int > cur;
  8.  
  9. void dfs(int v) {
  10.     if (used[v]) return;
  11.     used[v] = true;
  12.     cur.push_back(v + 1);
  13.     for (auto u : g[v]) {
  14.         dfs(u);
  15.     }
  16. }
  17.  
  18. int main() {
  19.     cin >> n >> m;
  20.     g.resize(n);
  21.     used.resize(n, false);
  22.     for (int i = 0; i < m; i++) {
  23.         int a, b;
  24.         cin >> a >> b;
  25.         a--; b--;
  26.         g[a].push_back(b);
  27.         g[b].push_back(a);
  28.     }
  29.     vector < vector < int > > ans;
  30.     for(int i = 0; i < n; i++) {
  31.         if (!used[i]) {
  32.             cur.clear();
  33.             dfs(i);
  34.             ans.push_back(cur);
  35.         }
  36.     }
  37.     cout << ans.size() << endl;
  38.     for (auto &e : ans) {
  39.         sort(e.begin(), e.end());
  40.         cout << e.size() << endl;
  41.         for (auto v : e) {
  42.             cout << v << " ";
  43.         }
  44.         cout << endl;
  45.     }
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement