MinhNGUYEN2k4

Untitled

Sep 27th, 2021
893
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define TASK "BLUEHOUSE"
  3. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  4. #define READFILE freopen(TASK".INP","r",stdin)
  5. #define WRITEFILE freopen(TASK".OUT","w",stdout)
  6. #define For(i,a,b) for(int i=a;i<=b;i++)
  7. #define Rep(i,a,b) for(int i=a;i>=b;i--)
  8. #define pb push_back
  9. #define ENDL '\n'
  10. #define debug(x) cout<<#x<<" = "<<x<<ENDL
  11. #define fi first
  12. #define se second
  13. #define ever (;true;)
  14. #define all(x) x.begin(),x.end()
  15. #define sz(a) ((int)(a).size())
  16. #define ms(a,x) memset(a,x,sizeof(a))
  17. #define int long long
  18.  
  19. using namespace std;
  20. typedef vector <int> vi;
  21. typedef pair <int,int> ii;
  22. typedef vector <ii> vpi;
  23. typedef pair <int,ii> iii;
  24. const int N = 50010;
  25. const int oo=0x3f;
  26. const int mod=1e9+7;
  27. const int dx[]={0,1,0,-1,0};
  28. int n,m,num[N],low[N],f[N],cnt,scc,tp[N],s[5];
  29. vpi edge;
  30. vi a[N],g[N];
  31. stack<int> st;
  32. void dfs(int u, int p){
  33.     num[u]=low[u]=++cnt;
  34.     st.push(u);
  35.     for (int v:g[u]){
  36.         if (v==p) continue;
  37.         if (num[v]) low[u]=min(low[u],num[v]);
  38.         else {
  39.             dfs(v,u);
  40.             low[u]=min(low[u],low[v]);
  41.             if (low[v]>=num[v]) edge.pb({u,v});
  42.         }
  43.     }
  44.     if (low[u]==num[u]){
  45.         int v;
  46.         scc++;
  47.         f[scc]=u;
  48.         do{
  49.             v=st.top();
  50.             st.pop();
  51.             tp[v]=scc;
  52.         } while (v!=u);
  53.     }
  54. }
  55. void dfs2(int u, int p){
  56.     if (a[u].size()==1 && u!=1) st.push(u);
  57.     for (int v:a[u]){
  58.         if (v==p) continue;
  59.         dfs2(v,u);
  60.     }
  61. }
  62. void init(){
  63.   FAST;
  64.   #ifndef ONLINE_JUDGE
  65.     READFILE;
  66.     WRITEFILE;
  67.   #endif
  68.   cin >> n >> m;
  69.   For(i,1,m){
  70.     int u,v;
  71.     cin >> u >> v;
  72.     g[u].pb(v);
  73.     g[v].pb(u);
  74.   }
  75. }
  76. signed main()
  77. {
  78.   init();
  79.   dfs(1,-1);
  80.   for (ii s : edge){
  81.     int u=s.fi;
  82.     int v=s.se;
  83.     a[tp[u]].pb(tp[v]);
  84.     a[tp[v]].pb(tp[u]);
  85.   }
  86.   dfs2(1,-1);
  87.   stack<ii> ss;
  88.   cnt=0;
  89.   while (st.size()){
  90.     s[++cnt]=st.top();
  91.     st.pop();
  92.     if (cnt==3){
  93.         ss.push({f[s[1]],f[s[3]]});
  94.         cnt=1;
  95.         s[1]=s[2];
  96.     }
  97.   }
  98.   if (cnt==2) ss.push({f[s[1]],f[s[2]]});
  99.   if (cnt==1 || a[1].size()==1) {
  100.     ss.push({f[s[1]],f[1]});
  101.     a[1].pb(2);
  102.   }
  103.   cout << ss.size() << ENDL;
  104.   while (ss.size()){
  105.     cout << ss.top().fi << ' ' << ss.top().se << ENDL;
  106.     ss.pop();
  107.   }
  108.   return 0;
  109. }
RAW Paste Data