orazma

a.cpp

Apr 18th, 2026
34
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 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. void is_point(int x){
  41.  
  42. }
  43.  
  44. void dfs2(int v, int pr = -1){
  45.     was[v] = 1;
  46.     tin[v] = ++timer;
  47.     fup[v] = tin[v];
  48.     int child = 0;
  49.     for (auto [to, num] : g[v]){
  50.         if (!was[to]){
  51.             child++;
  52.             dfs2(to, v);
  53.             fup[v] = min(fup[v], fup[to]);
  54.             if (tin[v] <= fup[to] && pr != -1){
  55.                 is_point(v);
  56.             }
  57.         }
  58.         else if (to != pr){
  59.             fup[v] = min(fup[v], tin[to]);
  60.         }
  61.     }
  62.     if (pr == -1 && child > 1){
  63.         is_point(v);
  64.     }
  65. }
  66.  
  67. void solve(){
  68.  
  69.     int n, m;
  70.     cin >> n >> m;
  71.  
  72.     for (int i = 1; i <= m; i++){
  73.         int x, y;
  74.         cin >> x >> y;
  75.         g[x].pb({y, i});
  76.         g[y].pb({x, i});
  77.     }
  78.  
  79.     for (int i = 1; i <= n; i++){
  80.         if (!was[i]){
  81.             dfs(i);
  82.         }
  83.     }
  84.     cout << ans.size() << '\n';
  85.     sort(ans.begin(), ans.end());
  86.     for (int x : ans){
  87.         cout << x << ' ';
  88.     }
  89.  
  90. }
  91.  
  92. int main() {
  93.     IOS;
  94.     freopen("bridges.in", "r", stdin);
  95.     freopen("bridges.out", "w", stdout);
  96.     int t = 1;
  97.    // cin >> t;
  98.     while(t--){
  99.         solve();
  100.     }
  101.     return 0;
  102. }
  103.  
  104.  
  105.  
Advertisement
Add Comment
Please, Sign In to add comment