Advertisement
Zuneve

и

Dec 31st, 2022
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5.  
  6.  
  7. void dfs(int v, vector <vector <int> > &g, vector <char> &used, vector <set<int>> &xx, set <int> &vv) {
  8. used[v] = true;
  9. vv.insert(v);
  10. for (int i = 0; i < g[v].size(); i++){
  11. if (used[g[v][i]] == 0){
  12. dfs(g[v][i], g, used, xx, vv);
  13. }
  14. }
  15. }
  16.  
  17. int main() {
  18. int n, m;
  19. cin >> n >> m;
  20. vector <vector <int>> g(n);
  21. for (int i = 0; i < m; i++) {
  22. int q, q1;
  23. cin >> q >> q1;
  24. q--;
  25. q1--;
  26. g[q].push_back(q1);
  27. g[q1].push_back(q);
  28. }
  29. int cmp_cnt=0;
  30. vector <char> used(n, false);
  31. vector <set<int>> xx(cmp_cnt); // компонента - вершины
  32. for (int i = 0; i<n; i++) {
  33. if (!used[i]) {
  34. set <int> vv; // вершины компоненты
  35. dfs(i,g,used, xx, vv);
  36. xx[cmp_cnt]=vv;
  37. cmp_cnt++;
  38. }
  39. } cout << cmp_cnt;
  40. for (int i = 0; i<cmp_cnt; i++) {
  41. cout << i << endl;
  42. for (auto c : xx[i]) cout << c << endl;
  43. }
  44. return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement