Salvens

A

Aug 12th, 2023
1,750
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <array>
  4. #include <vector>
  5. #include <numeric>
  6. #include <random>
  7. #include <chrono>
  8. #include <set>
  9. #include <map>
  10.  
  11. #define int long long
  12. using namespace std;
  13.  
  14. const long long INF = 1e9 + 7;
  15. const int MAXN = 2e4 + 1000;
  16. const int N = 1e5 + 10;
  17.  
  18. vector<vector<pair<int, int>>> g;
  19. array<int, MAXN> used, tin, up;
  20. int timer = 0;
  21. vector<int> ans;
  22.  
  23. void dfs(int v, int e = -1) {
  24.     used[v] = true;
  25.     tin[v] = up[v] = timer++;
  26.     for (auto [to, num]: g[v]) {
  27.         if (num == e) {
  28.             continue;
  29.         }
  30.         if (used[to]) {
  31.             up[v] = min(up[v], tin[to]);
  32.         } else {
  33.             dfs(to, num);
  34.             up[v] = min(up[v], up[to]);
  35.             if (up[to] > tin[v]) {
  36.                 ans.emplace_back(num);
  37.             }
  38.         }
  39.     }
  40. }
  41.  
  42. signed main() {
  43.     ios_base::sync_with_stdio(false);
  44.     cin.tie(nullptr);
  45.  
  46.     int n, m;
  47.     cin >> n >> m;
  48.     g.resize(n);
  49.     for (int i = 0; i < m; ++i) {
  50.         int u, v;
  51.         cin >> u >> v;
  52.         --u, --v;
  53.         g[u].emplace_back(v, i);
  54.         g[v].emplace_back(u, i);
  55.     }
  56.  
  57.     for (int i = 0; i < n; ++i) {
  58.         if (!used[i]) {
  59.             dfs(i);
  60.         }
  61.     }
  62.     cout << ans.size() << '\n';
  63.     sort(ans.begin(), ans.end());
  64.     for (auto& i: ans) {
  65.         cout << i + 1 << '\n';
  66.     }
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment