rembocoder

Untitled

May 2nd, 2023
878
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. vector<vector<int>> g;
  8. vector<int> depth;
  9. vector<int> up;
  10. vector<bool> used;
  11. vector<pair<int, int>> ans;
  12.  
  13. void dfs(int v, int p) {
  14.     used[v] = true;
  15.     up[v] = depth[v];
  16.     for (int to: g[v]) {
  17.         if (to == p) {
  18.             continue;
  19.         }
  20.         if (used[to]) {
  21.             up[v] = min(up[v], depth[to]);
  22.             continue;
  23.         }
  24.         depth[to] = depth[v] + 1;
  25.         dfs(to, v);
  26.         up[v] = min(up[v], up[to]);
  27.         if (up[to] == depth[to]) {
  28.             ans.push_back({v, to});
  29.         }
  30.     }
  31. }
  32.  
  33. int32_t main() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0); cout.tie(0);
  36.     int n, m;
  37.     cin >> n >> m;
  38.     g.resize(n);
  39.     for (int i = 0; i < m; i++) {
  40.         int a, b;
  41.         cin >> a >> b;
  42.         a--; b--;
  43.         g[a].push_back(b);
  44.         g[b].push_back(a);
  45.     }
  46.     used.assign(n, false);
  47.     depth.resize(n);
  48.     up.resize(n);
  49.     for (int i = 0; i < n; i++) {
  50.         if (!used[i]) {
  51.             dfs(i, -1);
  52.         }
  53.     }
  54.     cout << ans.size() << '\n';
  55.     for (int i = 0; i < ans.size(); i++) {
  56.         cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << '\n';
  57.     }
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment