Advertisement
kolbka_

Untitled

Jan 30th, 2022
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #include "optimization.h"
  11.  
  12. using namespace std;
  13. vector<vector<int>> tree;
  14. vector<bool> mark;
  15. map<pair<int, int>, bool> rebra;
  16. int n, e;
  17. map<pair<int, int>, pair<int, int>> mem;
  18. vector<int> time_;
  19. vector<int> min_time;
  20. int T = 0;
  21. vector<int>result;
  22. int dfs(int root, int parent) {
  23.     time_[root] = min_time[root] = ++T;
  24.     for (auto x : tree[root]) {
  25.         if (x == parent) continue;
  26.         if (time_[x] == 0){
  27.             dfs(x, root);
  28.             if (min_time[x] > time_[root]  && mem[{min(x, root), max(x,root)}].second == 1){
  29.                 result.push_back(mem[{min(x, root), max(x,root)}].first);
  30.             }
  31.             min_time[root] = min(min_time[root], min_time[x]);
  32.         }
  33.         else{
  34.             min_time[root] = min(min_time[root], time_[x]);
  35.         }
  36.     }
  37. }
  38.  
  39.  
  40. int main() {
  41.     cin >> n >> e;
  42.     mark.resize(n+1, false);
  43.     tree.resize(n+1);
  44.     time_.resize(n+1);
  45.     min_time.resize(n+1);
  46.     for (int i = 1; i <= e; i++) {
  47.         int a, b;
  48.         cin >> a >> b;
  49.         if (a > b){
  50.             swap(a,b);
  51.         }
  52.         if (mem.count({a,b}) == 0){
  53.             mem[{a, b}] = {i, 1};
  54.         }
  55.         else{
  56.             mem[{a, b}].second += 1;
  57.         }
  58.         tree[a].push_back(b);
  59.         tree[b].push_back(a);
  60.     }
  61.     dfs(1, 0);
  62.     cout << result.size() << '\n';
  63.     for (auto x : result){
  64.         cout << x << '\n';
  65.     }
  66. }
  67.  
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement