Advertisement
kolbka_

Untitled

Feb 4th, 2022
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13. #include <iostream>
  14. #include <vector>
  15. #include <string>
  16. #include <stack>
  17. #include <set>
  18. #include <map>
  19. #include "optimization.h"
  20. #include <unordered_map>
  21. using namespace std;
  22. vector<vector<int>> tree;
  23.  
  24. int n, e;
  25. map<pair<int, int>, int> mem;
  26. vector<int> time_;
  27. vector<int> min_time;
  28. stack<int> stack_;
  29. int T = 0;
  30. vector<vector<int>> result;
  31. multiset<pair<int,int>> mark;
  32. void relax(int &a, int &b) {
  33.     if (b < a) {
  34.         a = b;
  35.     }
  36. }
  37.  
  38. void dfs(int root, int parent) {
  39.     stack_.push(root);
  40.     time_[root] = min_time[root] = ++T;
  41.     for (auto x: tree[root]) {
  42.         if (x == parent) continue;
  43.         if (!time_[x]) {
  44.             int stack_lvl = stack_.size();
  45.             dfs(x, root);
  46.             relax(min_time[root], min_time[x]);
  47.             if (min_time[x] > time_[root] && (mark.count({min(root,x), max(root,x)}) == 1)) {
  48.                 vector<int> tmp;
  49.                 while (stack_.size() > stack_lvl) {
  50.                     tmp.push_back(stack_.top());
  51.                     stack_.pop();
  52.                 }
  53.                 if (!tmp.empty()) result.push_back(tmp);
  54. //                result.insert(y);
  55.             }
  56.         } else {
  57.             relax(min_time[root], time_[x]);
  58.         }
  59.     }
  60. }
  61.  
  62.  
  63. int main() {
  64. //    cin >> n >> e;
  65.     n = readInt();
  66.     e = readInt();
  67. //    mark.resize(n+1, vector<int>(n+1, 0));
  68.     tree.resize(n + 1);
  69.     time_.resize(n + 1, 0);
  70.     min_time.resize(n + 1);
  71.     for (int i = 1; i <= e; i++) {
  72.         int a, b;
  73. //        cin >> a >> b;
  74.         a = readInt();
  75.         b = readInt();
  76.         if (a > b) {
  77.             swap(a, b);
  78.         }
  79.         mark.insert({a,b});
  80.         tree[a].push_back(b);
  81.         tree[b].push_back(a);
  82.     }
  83.  
  84.     for (int v = 1; v <= n; v++) {
  85.         int stack_lvl = stack_.size();
  86.         if (time_[v] == 0) { dfs(v, 0); }
  87.         vector<int> tmp;
  88.         while (stack_.size() > stack_lvl) {
  89.             tmp.push_back(stack_.top());
  90.             stack_.pop();
  91.         }
  92.         if (!tmp.empty()) {
  93.             result.push_back(tmp);
  94.         }
  95.     }
  96.     for (auto &x : result){
  97.         sort(x.begin(), x.end());
  98.     }
  99.     sort(result.begin(), result.end());
  100. //    cout << result.size() << '\n';
  101.     writeInt(result.size(), '\n');
  102.  
  103.     for (auto &x: result) {
  104. //        cout << x << '\n';
  105. //        sort(x.begin(), x.end());
  106.         for (auto &y: x) {
  107.             writeInt(y, ' ');
  108. //            cout << y << " ";
  109.         }
  110.         writeChar('\n');
  111. //cout << '\n';
  112.     }
  113. }
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement