Advertisement
MinhNGUYEN2k4

Untitled

Aug 6th, 2020
125
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. #define int long long
  3. #define MIN(x,y) {if (x > (y)) x = (y)}
  4. #define MAX(x,y) {if (x < (y)) x = (y)}
  5. using namespace std;
  6. const int N = 10005;
  7. typedef pair<int,int> ii;
  8.  
  9. vector<int> a[N];
  10. int n,m,par[N];
  11. int num[N],low[N], cnt = 0;
  12. vector<ii> res;
  13.  
  14. void dfs(int u)
  15. {
  16.     low[u] = num[u] = ++ cnt;
  17.     for(int i = 0; i < a[u].size(); ++i)
  18.     {
  19.         int v = a[u][i];
  20.         if (v == par[u]) continue;
  21.         if (par[v]) low[u]=min(low[u],num[v]);
  22.         else
  23.         {
  24.             par[v]=u;
  25.             dfs(v);
  26.             low[u]=min(low[u],low[v]);
  27.             if (low[v] == num[v]) res.push_back(ii(u,v));
  28.         }
  29.     }
  30. }
  31.  
  32. signed main()
  33. {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);cout.tie(0);
  36.     freopen("cbridge.inp","r",stdin);
  37.     freopen("cbridge.out","w",stdout);
  38.     cin >> n >> m;
  39.     for(int i=1; i<=m; ++i)
  40.     {
  41.         int u,v;
  42.         cin >> u >> v;
  43.         a[u].push_back(v);
  44.         a[v].push_back(u);
  45.     }
  46.     for(int i=1; i<=n; ++i)
  47.     {
  48.         if (!par[i])
  49.         {
  50.             par[i]=-1;
  51.             dfs(i);
  52.         }
  53.     }
  54.     cout << res.size() << endl;
  55.     for(ii x : res) cout << x.first << " " << x.second << endl;
  56.     return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement