orazma

a.cpp

Apr 18th, 2026
28
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. #define pb push_back
  5. #define mp make_pair
  6. #define ll long long
  7.  
  8. #define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  9.  
  10. using namespace std;
  11. const int INF = 1e9 + 1;
  12. const int MAXN = 4e5 + 10;
  13. int tin[MAXN], fup[MAXN], timer;
  14. bool was[MAXN];
  15. vector <int> ans;
  16. vector <pair <int, int> > g[MAXN];
  17.  
  18. void is_bridge(int x){
  19.     ans.pb(x);
  20. }
  21.  
  22. void dfs(int v, int pr = -1){
  23.     was[v] = 1;
  24.     tin[v] = ++timer;
  25.     fup[v] = tin[v];
  26.  
  27.     for (auto [to, num] : g[v]){
  28.         if (!was[to]){
  29.             dfs(to, v);
  30.             fup[v] = min(fup[v], fup[to]);
  31.             if (tin[v] < fup[to]){
  32.                 is_bridge(num);
  33.             }
  34.         }
  35.         else if (to != pr){
  36.             fup[v] = min(fup[v], tin[to]);
  37.         }
  38.     }
  39. }
  40.  
  41. void solve(){
  42.  
  43.     int n, m;
  44.     cin >> n >> m;
  45.  
  46.     for (int i = 1; i <= m; i++){
  47.         int x, y;
  48.         cin >> x >> y;
  49.         g[x].pb({y, i});
  50.         g[y].pb({x, i});
  51.     }
  52.  
  53.     for (int i = 1; i <= n; i++){
  54.         if (!was[i]){
  55.             dfs(i);
  56.         }
  57.     }
  58.     cout << ans.size() << '\n';
  59.     sort(ans.begin(), ans.end());
  60.     for (int x : ans){
  61.         cout << x << ' ';
  62.     }
  63.  
  64. }
  65.  
  66. int main() {
  67.     IOS;
  68.     freopen("bridges.in", "r", stdin);
  69.     freopen("bridges.out", "w", stdout);
  70.     int t = 1;
  71.    // cin >> t;
  72.     while(t--){
  73.         solve();
  74.     }
  75.     return 0;
  76. }
  77.  
  78.  
  79.  
Advertisement
Add Comment
Please, Sign In to add comment