Advertisement
NgJaBach

Cut Bridges

Jul 13th, 2022
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. // NgJaBach: Forever Meadow <3
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6. typedef long long int ll;
  7. typedef unsigned long long ull;
  8. #define pb push_back
  9. #define pob pop_back
  10. #define mp make_pair
  11. #define upb upper_bound
  12. #define lwb lower_bound
  13. #define bend(a) a.begin(),a.end()
  14. #define rev(x) reverse(bend(x))
  15. #define mset(a) memset(a, 0, sizeof(a))
  16. #define fi first
  17. #define se second
  18. #define gcd __gcd
  19. #define getl(s) getline(cin, s);
  20. #define setpre(x) fixed << setprecision(x)
  21. #define endl '\n'
  22. const int N=200050,M=1000000007;
  23. const ll INF=1e18+7;
  24. int cnt=0,dis[N],low[N];
  25. vector<int>gay[N];
  26. vector<pair<int,int> >bridges;
  27. void dfs(int u,int p){
  28.     low[u]=dis[u]=cnt++;
  29.     for(auto v:gay[u]){
  30.         if(v!=p){
  31.             if(dis[v]!=-1){
  32.                 low[u]=min(low[u],dis[v]);
  33.             }
  34.             else{
  35.                 dfs(v,u);
  36.                 low[u]=min(low[u],low[v]);
  37.                 if(dis[v]<=low[v]){
  38.                     bridges.pb({min(u,v),max(u,v)});
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     return;
  44. }
  45. int main(){
  46.     ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  47. //    freopen(".inp","r",stdin);
  48. //    freopen(".out","w",stdout);
  49.     int n,m,x,y;
  50.     cin>>n>>m;
  51.     while(m--){
  52.         cin>>x>>y;
  53.         gay[x].pb(y);
  54.         gay[y].pb(x);
  55.     }
  56.     for(int i=1;i<=n;++i) dis[i]=-1;
  57.     for(int i=1;i<=n;++i){
  58.         if(dis[i]==-1) dfs(i,i);
  59.     }
  60.     n=bridges.size();
  61.     sort(bend(bridges));
  62.     cout<<n<<endl;
  63.     for(int i=0;i<n;++i) cout<<bridges[i].fi<<" "<<bridges[i].se<<endl;
  64.     return 0;
  65. }
  66. /*
  67. ==================================+
  68. INPUT:                            |
  69. ------------------------------    |
  70.  
  71. ------------------------------    |
  72. ==================================+
  73. OUTPUT:                           |
  74. ------------------------------    |
  75.  
  76. ------------------------------    |
  77. ==================================+
  78. */
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement